LeetCode - Maximum Depth of Binary Tree 풀이

문제

💡 주어진 이진 트리의 노드의 최대 깊이를 구하시오.

예시

• Input: root = [3,9,20,null,null,15,7]
• Output: 3

제약 조건

• 트리의 노드 수는 [0, 10^4] 범위 안에 있습니다.
• 노드 값의 범위는 -100부터 100 까지다.

문제 링크 -> Maximum Depth of Binary Tree - LeetCode

풀이 - Level Order

문제 이해하기

• 시간복잡도를 계산한기 위한 N은 트리의 노드 갯수다.
• input의 최댓값에 따라 N^2 보다 작은 시간복잡도를 가진 알고리즘을 선택해야한다.
• 노드 값의 범위는 int 형 변수에 담을 수 있다.
• 노드 갯수가 0개일 때 예외처리가 필요하다.
• 노드 값은 중복될 수 있다.

접근 방법 생각하기

• 노드의 레벨을 따라 탐색하면서 최대 깊이를 구한다.

코드 설계

• 노드를 담아 놓을 Queue 를 생성한다.
• root 노드를 생성한 큐에 저장한다.
• root 노드가 있다면 현재 깊이는 1이다.
• 큐에서 요소를 꺼내서 노드의 왼쪽 자손과 오른쪽 자손을 다시 큐에 집어 넣는다.
• 자손 노드가 있는 경우 현재 깊이에서 1을 더한다.
• 현재 노드가 최대 깊이보다 크다면 최대 깊이에 대입한다.

코드 구현

class NodeWithDepth {
    TreeNode node;
    int depth;

    NodeWithDepth(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

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

    Queue<NodeWithDepth> queue = new LinkedList<>();
    queue.offer(new NodeWithDepth(root, 1));
    int maxDepth = 0;

    while (!queue.isEmpty()) {
        NodeWithDepth current = queue.poll();
        TreeNode node = current.node;
        int depth = current.depth;

        // 현재 노드의 깊이를 업데이트
        maxDepth = Math.max(maxDepth, depth);

        if (node.left != null) {
            queue.offer(new NodeWithDepth(node.left, depth + 1));
        }
        if (node.right != null) {
            queue.offer(new NodeWithDepth(node.right, depth + 1));
        }
    }

    return maxDepth;
}

풀이 - Post Order

문제 이해하기

• 시간복잡도를 계산한기 위한 N은 트리의 노드 갯수다.
• input의 최댓값에 따라 N^2 보다 작은 시간복잡도를 가진 알고리즘을 선택해야한다.
• 노드 값의 범위는 int 형 변수에 담을 수 있다.
• 노드 갯수가 0개일 때 예외처리가 필요하다.
• 노드 값은 중복될 수 있다.

접근 방법 생각하기

• 재귀적으로 노드의 깊이를 탐색해본다.
• leaf 노드일 때의 깊이를 1이라고 하고 상위 노드로 올라 갈 때마다 깊이를 1 더한다.

코드 설계

• postorder 방식으로 노드를 탐색한다.
• leaf 노드를 방문 할 때 깊이 1을 반환하고 이후 노드를 차례로 방문 하면서 깊이에 1을 더한다.
• 양 쪽 서브트리의 깊이가 다른 경우 깊이가 깊은 쪽을 선택하여 1을 더한다.

코드 구현

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    return Math.max(leftDepth, rightDepth) + 1;
}