Leetcode 104. Maximum Depth of Binary Tree with Python

문제

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes 
along the longest path from the root node down to the farthest leaf node.

이진트리의 루트가 주어질 때, 트리의 최고 높이를 리턴하시오.

예시

• Input: root = [3,9,20,null,null,15,7]
• Output: 3

제한

• The number of nodes in the tree is in the range [0, 104].
• 100 <= Node.val <= 100

풀이

끝에 도달시 1 리턴
한쪽이라도 자식이 있으면 그쪽 높이 + 1 리턴
두쪽 다 자식이 있으면 두 자식의 높이중 높은것 + 1 리턴

으로 재귀식을 구현하면 된다.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None: return 0
        if root.left == None and root.right == None: return 1
        elif root.left == None: return self.maxDepth(root.right) + 1
        elif root.right == None: return self.maxDepth(root.left) + 1
        else: return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

주의할점은 아예 노드가 하나 없는 root가 테스트케이스에 있다는 점이다.