【LeetCode】104. Maximum Depth of Binary Treeを解く

問題へのリンク

問題概要

二分木rootが与えられるので，最大の深さを求める．
ここで，最大の深さとは根から始まる最も長いパスに含まれるノードの数のことを指す．

例えば，以下の例では「3→20→7」（「3→20→15」も可）のパスが最長となるため答えとして3を返せばi良い．

制約

• ノードの数$0 \leq N \leq10^4$
• ノードの値$-11 \leq Node.val \leq 100$

考えたこと

再帰的に実装する．

まず，ノードの数は0以上なのでroot = []のとき0を返すことが分かる．

また，root != []の場合を考えるとroot.leftとroot.rightのうち「パスが長い方の深さ＋１」が答えとなる．

従って，以下のように実装すればよいことが分かる：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))