Leetcode - 104. Maximum Depth of Binary Tree

문제

풀이

이진트리는 자식 노드가 2개인 특성 때문에 재귀적으로 풀이가 가능하다. 따라서 DFS 재귀로 구현했다.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        def traverse(node, depth):
            if node.left is None and node.right is None:
                return depth

            left_depth = right_depth = 0
            if node.left is not None:
                left_depth = traverse(node.left, depth + 1)
            if node.right is not None:
                right_depth = traverse(node.right, depth + 1)

            return max(left_depth, right_depth)

        depth = 0
        if not root:
            return depth
        else:
            return traverse(root, depth + 1)

이 문제는 BFS로도 풀 수 있다.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        depth = 0

        if root:
            queue = []
            depth = 1
            if root.left is not None:
                queue.append((root.left, 1))
            if root.right is not None:
                queue.append((root.right, 1))

            while queue:
                next, cur_depth = queue.pop(0)
                if next.left is not None:
                    queue.append((next.left, cur_depth + 1))
                if next.right is not None:
                    queue.append((next.right, cur_depth + 1))
                depth = cur_depth + 1

        return depth

BFS==queue 를 기억하자! 책에서는 collections.deque 를 사용해서 풀었다.

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)

        return depth

dequeue가 list로 구현한 스택, 큐보다 항상 빠른 $O(1)$ 에 양방향 노드를 추출할 수 있기 때문에 효율적이고, TreeNode 를 바로 queue로 만들 수 있어서 간단하다. 코딩테스트에서는 이렇게 풀어도 좋겠지만 인터뷰에서는 dequeue 없이 풀어보라고 할 수 있으니 모든 풀이방법을 기억할 것!