[Leetcode 104] Maximum Depth of Binary Tree (Java)

문제 링크: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

이 문제는 트리의 최대 깊이를 구하는 문제이다. 깊이란, 루트부터 현재 노드까지의 거리를 뜻하므로, 최대 깊이는 리프 노드들 중에서 구할 수 있을 것이다.

주의해야할 점은, 리프 노드이면 최대 깊이를 가질 수 있는 후보인 것이지, 무조건 리프 노드를 방문 했을 때의 깊이를 리턴하면 안된다.

따라서, 모든 노드를 탐색해가면서 리프 노드들을 모두 방문해 주어야하므로 DFS나 BFS를 통해 문제를 해결할 수 있을 것이다.

풀이 1. BFS (Level Order)

트리에서 BFS는 결국 level order(레벨 순회)이다. 이러한 특성을 살려, 반복문을 작성할 때 같은 레벨에 있는 노드들을 한 번에 처리하고 depth를 1 증가 시키는 것이 좋아보인다.

이를 코드로 옮기면 다음과 같다.

class Solution1 {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.add(root);

        while (!queue.isEmpty()) {
            depth++;
            int qSize = queue.size();
            for (int i = 0; i < qSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }

        return depth;
    }
}

풀이 2. DFS

이 문제의 경우 DFS는 재귀 구조로 푸는 것이 간단해 보인다.

애초에, maxDepth메서드가 트리의 최대 깊이를 리턴하는 구조이기 때문에, 왼쪽 서브트리의 최대 깊이와 오른쪽 서브트리의 최대 깊이 중 최대 값을 택하면 되기 때문이다.

이를 코드로 옮기면 다음과 같다.

class Solution2 {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;
        return Math.max(left, right);
    }
}