[Leetcode 104] - Maximum Depth of Binary Tree w/ 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.

 

 

이진 트리가 주어졌을때 깊이를 찾아내라는 문제

 

 

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

 

 

---

 

 

 

Example 1:

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

 

 

Example 2:

Input: root = [1,null,2]
Output: 2

 

 

---

 

 

 

트리에서 깊이를 찾아내야 되기 때문에 DFS를 사용

 

1. 왼쪽 또는 오른쪽을 최대로 들어가기

2. 자식 노드가 없을시 1으로 시작 -> 리턴

3. 루트로 돌아와 왼쪽 오른쪽 숫자 비교

 

 

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0
            
        if not (root.left or root.right): 
            return 1
        
        left = 1 + self.maxDepth(root.left)
        right = 1 + self.maxDepth(root.right)

        return max(left, right)