Maximum Deptgh of BinaryTree

문제 간단 설명

이진 트리가 주어질 때 가장 깊은 곳의 Depth를 구하라

Level Order 풀이

접근 방법을 생각할 때 Level Order로 풀었을 경우, while문에서 어떻게 max_node를 구해야하지? 하는 생각이 들었다. 모든 노드에 접근할 때마다 depth를 올려주면 안되기 때문이다. 여기에서 tuple을 이용해서 cur_node에 따른 cur_depth를 구해주는 스킬을 배웠다.

class Solution :
  def maxDepth(self, root:TreeNode) -> int:
    max_depth = 0
    if root is None : 
      return max_depth
    
    max_depth = 1
    q = deque()
    q.append((root, max_depth))
    
    while q : 
      cur_node, cur_depth = q.popleft()
      max_depth = max(max_depth, cur_depth)
      
      if cur_node.left :
        q.append((cur_node.left, cur_depth + 1))
        
      if cur_node.right :
        q.append((cur_node.right, cur_depth + 1))
      
    return max_depth
    
print(Solution().maxDepth(cur_node))

Post Order 풀이

class Solution :
  def maxDepth(self, cur_node:TreeNode) -> int:
    max_depth = 0
    if cur_node is None : 
      return max_depth
    
    left = self.maxDepth(cur_node.left)
    right = self.maxDepth(cur_node.right)
    
    return max(left, right) + 1

가장 작은 조상 빗물 트래핑(틀림)