[Leetcode/파이썬] 104. Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

---

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root :
            return 0

        leftnode = self.maxDepth(root.left)
        rightnode = self.maxDepth(root.right)

        return max(leftnode, rightnode) + 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root :
            return 0
        
        q = deque()
        q.append(root)

        depth = 0
        while q :
            depth += 1

            for _ in range(len(q)) :
                cur = q.popleft()
                if cur.left :
                    q.append(cur.left)
                if cur.right :
                    q.append(cur.right)

        return depth

1번 풀이는 DFS, 2번 풀이는 BFS 풀이었다. 생각보다 조금 헤맸지만 내가 생각했던 풀이대로 나온 것 같아서 기쁘다. 

우선 DFS. 이 풀이는 생각보다 그림을 그릴 줄 알면 쉽게 풀리는 문제이다. 그러나 나는 return +1 이 부분에서 이해가 잘 되지 않아서 스터디 시간에 이 + 1 이 어떻게 동작하는지에 대해서 질문을 좀 하고싶다. 

1. 저 +1 이 어디에 저장되는지
2. 총 depth 저장 위치 => 같은 질문인가? 여튼.

두 번째는 BFS. 사실 이 풀이를 생각하면서 가장 먼저 떠오른 풀이는 이 풀이였다. 최근 리트코드를 풀면서 BFS 중 while 내에 for len(q) 까지 하는 이중 반복문으로 BFS를 제어하는 것이 심심치 않게 나와서 이 내용을 채용하여 문제를 해결하려고 했었다. depth += 1 의 위치 문제 때문에 조금 많이 헤맸지만, 무난히 문제를 해결하였다. flag = False, True 로 두고 문제를 해결하고도 했었는데 쉽지 않아서 다른 분의 코드를 참고 했더니 while q 바로 아래 depth += 1 을 하게 되면 쉽게 문제를 해결할 수 있을 것이다.