[LEET CODE] 104. Maximum Depth of Binary Tree

# Problem

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. Constraints: The number of nodes in the tree is in the range [0, 104]. -100 <= Node.val <= 100

 

# My Answer

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

 

# Solution 1 - 반복 구조로 BFS 풀이

import collections

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue = collections.deque([root])
        depth = 0

        while queue:
            depth += 1
            # 큐 연산 추출 노드의 자식 노드 삽입
            for _ in range(len(queue)):
                cur_root = queue.popleft()
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        # BFS 반복 횟수 == 깊이
        return depth

for 문에서 부모노드의 길이 만큼만 반복

부모 노드가 모두 추출된 이후 다시 while문을 통해 다음 깊이의 노드 반복

 

BFS에서는 while문의 반복 횟수가 높이