Tree: 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

 

https://youtu.be/meKRO8w6KT8?si=dDC-xWB8fOBdng6_

 

 

1. 스텍을 이용: 

• 깊이 우선 탐색 할때 주로 스텍을 사용
• 스텍에, [(노드값, 깊이), ...] 이런식으로 추가
• 스텍 팝 하고.. 그 자식노드를 스텍에 추가.. 하는 식으로..
• time: O(n)
• space: O(n)

 

```
# 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:  # root 가 null 이면
            return 0
        max_depth = 0
        stack = [(root, 1)] # 최상위노드 root 와 그의 깊이인 1을 저장

        while stack: # stack 에 값이 있는동안 계속 실행
            node, depth = stack.pop()
            max_depth = max(max_depth, depth) # depth 갱신

            if node.left:
                stack.append((node.left, depth+1))
            if node.right:
                stack.append((node.right, depth+1))
        
        return max_depth

 

2. 재귀 방법: 

• 아래서 , 즉, 최하위 노드(이게, 깊이가 1)에서, 거꾸로 올라오는 방법
• 자식 노드의 깊이들 중 최대값에서 1 더해서 자기 깊이로 가져감
• time: O(n)
• space: O(n)

 

# 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: # root, 현재 노드가 null 이면, 0 반환
            return 0

        # 현재 노드도 감안해야되서 1을 더해줌, 
        # 현재 노드가 null 이면, 0 반환하므로, 즉, 자식이 없으면, 1을 리턴하게 됨
        return 1 + max(
            self.maxDepth(root.left),
            self.maxDepth(root.right)
        )

 

깊이 묻는 문제니깐..BFS로 

# 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:
        # depth -> bfs : 큐로
        # root: depth 1 부터
        if not root: # root 없으면
            return 0
            
        depth = 0
        q = deque([root])

        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node.left: # 있으면 추가
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            depth += 1
            print(depth)
        
        return depth