Leetcode - 104. Maximum Depth of Binary Tree

 

이진 트리의 최대 길이(Maximum Depth of Binary Tree) 문제이다.

이진 트리의 루트 노드가 주어졌을 때, 트리의 최대 깊이를 반환해야 한다.

-> 최대 깊이란? 루트 노드에서 가장 깊은 리프 노드까지 도달하는 경로에 있는 노드의 개수를 의미함.

 

        3
       / \
      9  20
         / \
        15  7

 

주어진 트리의 모형을 보면 가장 깊은 경로는 3 -> 20 -> 15 or 7 로써 트리의 최대 깊이는 3임.

 

첫번째 풀이 방식: DFS방식(재귀 방식)

뿌리 -> 자식 -> 자식... 이런식으로 한쪽 끝까지 파고 들어가면서 탐색함

루트 노드부터 왼쪽, 오른쪽 자식을 모두 방문하면서 "왼쪽 서브트리의 깊이", "오른쪽 서브트리의 깊이"를 각각 구하고

둘중 더 큰 값에 1을 더해 현재 깊이를 계산함.

 

TreeNode 클래스의 사용

TreeNode 클래스는 이진 트리의 구조를 코드로 표현하기 위해 사용되는 핵심적인 클래스

       1
      / \
     2   3

위 처럼 이진트리는 이렇게 생김.

이걸 코드로 표현하려면 하나의 노드가 값을 하나 가지고 있어야하고, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리킬 수 있어야 함.

 

class TreeNode {
	int val; // 노드에 저장된 값
    TreeNode left; // 왼쪽 자식 노드
    TreeNode right; // 오른쪽 자식 노드
    
   TreeNode(int val) {
   		this.val = val;  // 값을 받아서 노드 만듬
       }
    }

 

 

직접 트리를 만들어보면

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

 

이렇게 만들어주면 위에 있는 이진트리가 완성됨.

 

 

우리가 현재 풀고있는 문제에서는 LeetCode가 백그라운드에서 TreeNode를 우리가 직접 하나하나 연결하지 않아도 자동으로 배열을 트리로 만들어줌

 

 

 

문제 풀이

1. 종료 조건을 설정해줌

만약 해당 root가 Null이라면 0을 리턴해줌 (트리가 비어있거나 root 자체가 null인 경우)

 // 종료 조건
        if (root == null) {
            return 0;
        }

 

2. 왼쪽, 오른쪽 자식의 깊이를 재귀로 구하기

 int leftDepth = maxDepth(root.left);
 int rightDepth = maxDepth(root.right);

왼쪽 서브트리의 깊이와 오른쪽 서브트리의 깊이를 재귀를 통해 구해줌

-> 재귀 호출이 계속 되어서 내려가며 가장 아래 리프 노드까지 탐색됨.

 

3. 더 값이 큰 깊이값에 대해 1을 더해서 반환

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

왼쪽과 오른쪽을 비교하여 더 깊은 값에 대해서 1을 더하여 반환해줌 (현재 이 노드또한 깊이에 포함 되기 때문)

 

최종 코드

class Solution {
    public int maxDepth(TreeNode root) {
        // 종료 조건
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

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

}

 

 

실행 순서

        3
       / \
      9   20
          / \
        15   7

 

maxDepth(3) : 자식들로 재귀

maxDepth(9) -> 자식들 둘다 Null -> 0

leftDepth = 0, rightDepth = 0 -> left rigth둘다 Null이라 0으로 올라오고 그 둘중 더 큰값(어차피 둘다 0)을 +1하여 최종적으로 반환함 -> return 1

 

maxDepth(20) : 자식들로 재귀

 - maxDepth(15) -> 자식들 둘다 Null -> 0

 - maxDepth(7) -> 자식들 둘다 null -> 0

둘다 0, 0 이니까 1씩 더해서 return 1, return 1

그럼 maxDepth(20)에서의 leftDepth, rightDepth는 각각 1,1 둘 중 큰거에 +1 해야하는데 어차피 둘다 1이니 return 2

 

최종적으로 maxDepth(3)에서의 leftDepth는 1, rightDepth는 2

둘중 큰건 2에 +1을 담아 return 해주면 3.

 

그래서 최종적으로 3이라는 결과값이 도출됨.

 

 

 

두번째 풀이 방식: BFS 방식

BFS는 루트부터 시작해서 같은 레벨의 노드를 먼저 탐색

 

깊이를 1부터 시작해서, 각 레벨은 Queue에 저장해가며, 한 레벨씩 순차적으로 탐색함.

 

우선 종료조건은 dfs와 동일하게 설정해준후

 

deque를 사용하여 deque에 노드가 빌때까지 bfs로 탐색해주어 깊이가 한번씩 늘어날수록 깊이를1씩 증가하여 최종적으로 깊이를 반환 해주었음.

class Solution {
    public int maxDepth(TreeNode root) {
        // 종료 조건
        if (root == null) {
            return 0;
        }

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        int depth = 0;

        while(!deque.isEmpty()) {
            int size = deque.size();

            for(int i = 0; i < size; i++) {
                TreeNode currentNode = deque.pollFirst();
                
                if (currentNode.left != null) {
                    deque.addLast(currentNode.left);
                }

                if (currentNode.right != null) {
                    deque.addLast(currentNode.right);
                }
            }
            // 한번 돌았으니 depth 증가
            depth++;
        }

        return depth;

    }

}

 

결과를 보면 이 문제에서는 dfs가 bfs보다 성능이 좀 더 좋게 나옴.