[LeetCode] 104. Maximum Depth of Binary Tree

문제

Binary Tree 의 depth를 구하는 문제였음

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

일단, 정처기 공부에서 읽고 끝낸 트리 노드 구조에 대해 다시 정리를 해보자.

Binary Tree Node(이진 트리 노드)는 각 노드가 최대 2개의 자식 노드를 가질 수 있고, 아래와 같은 규칙을 가짐

왼쪽 자식 노드 < 부모 노드

오른쪽 자식 노드 > 부모 노드

그리고 자식이 없는 노드는 리프 노드라고 함

 

트리 탐색 방법은 아래와 같음

1. 전위 순회: 루트 -> 왼쪽 -> 오른쪽

ex) 3 - 9 - 20 - 15 - 7

2. 중위 순회: 왼쪽 -> 루트 -> 오른쪽

ex) 9 - 3 - 15 - 20 - 7

3. 후위 순회: 왼쪽 -> 오른쪽 -> 루트

ex) 9 - 15 - 7 - 20 - 3

 

아이디어

input 배열은 BFS 순서로 레벨 순서로 들어옴

왼쪽 트리 노드들과 오른쪽 트리 노드들을 재귀 방식으로 풀어보고 더 큰 값에 root +1을 하기로 함 -> DFS(깊이 우선 탐색 방식)

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;
}

후위 순위 방식으로 간단하게 풀었는데, 다른 방식으로도 풀어보려 함 (이건 자식 노드들을 먼저 방문해서 탐색해서 현재 노드 깊이를 산출해내는 방식)

1. maxDepth(3)
   1. maxDepth(9)
      1. maxDepth(null) = 0
      2. maxDepth(null) = 0
      3. return max(0, 0) + 1 = 1
   2. maxDepth(20)
      1. maxDepth(15)
         1. maxDepth(null) = 0
         2. maxDepth(null) = 0
         3. return max(0, 0) + 1 = 1
      2. maxDepth(7)
         1. maxDepth(null) = 0
         2. maxDepth(null) = 0
         3. return max(0, 0) + 1 = 1
   3. return max(1, 1) + 1 = 2
2. return max(1, 2) + 1 = 3

DFS(깊이 우선 탐색)으로 반복문을 사용하여 작성하면 아래와 같음 -> (노드, 현재 깊이)를 저장하고 꺼내면서 최대 깊이를 갱신하는 방식

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

    Stack<TreeNode> nodeStack = new Stack<>();
    Stack<Integer> depthStack = new Stack<>();

    nodeStack.push(root);
    depthStack.push(1);

    int maxDepth = 0;

    while (!nodeStack.isEmpty()) {
        TreeNode node = nodeStack.pop();
        int depth = depthStack.pop();

        if (node != null) {
            maxDepth = Math.max(maxDepth, depth);

            // 오른쪽을 먼저 push하면 왼쪽이 나중에 pop되어 전위 순서 유지
            if (node.right != null) {
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
            }
            if (node.left != null) {
                nodeStack.push(node.left);
                depthStack.push(depth + 1);
            }
        }
    }

    return maxDepth;
}

 

BFS(너비 우선 탐색)은 레벨 순서로 들어온 input 트리를 탐색하면서 각 레벨마다 카운트를 1씩 증가시키는 방식

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

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

    while (!queue.isEmpty()) {
        int size = queue.size(); // 현재 레벨에 있는 노드 개수
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll(); // 현재 레벨의 노드 하나 꺼내기
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++; // 한 레벨 탐색 완료할 때마다 깊이 +1
    }

    return depth;
}

1. 3 -> depth = 1
2. 9, 20 -> depth = 2
3. 15, 7 -> depth = 3
4. queue가 빈큐가 되면 탐색 종료하고 리턴