[LeetCode] 104. Maximum Depth of Binary Tree

class Solution {
    public int maxDepth(TreeNode root) {    
        if (root == null) { //해당 노드가 null 이라면 0을 반환
            return 0; 
        }
    
        int leftDepth = maxDepth(root.left); //왼쪽 줄기의 깊이를 계산
        int rightDepth = maxDepth(root.right); // 오른쪽 줄기의 깊이를 계산
        
        return Math.max(leftDepth, rightDepth) + 1; // 왼쪽과 오른쪽 중 더 큰쪽에 1을 더하여 반환
    }
}

 

우선 왼쪽부터 시작하여 가장 깊은 곳에 위치한 node까지 찾아간다.

거기서부터 차례대로 올라가며 깊이 값에 1을 더해간다.

 

1번 루트노드에서 시작하여 maxDepth(root.left)를 통해 가장 마지막 4번 노드까지 간다.

4번 노드에서 maxDepth(root.left)와 maxDepth(root.right)를 통해 나오는 값은 두 노드 모두 Null 이기 때문에 0이다.

그럼 4번 노드에서의 leftDepth와 rightDepth는 각각 0과 0이다.

이제 4번 노드에서의 Math.max(leftDepth, rightDepth) + 1 은 Math.max(0, 0) + 1이므로 1을 반환 한다.

 

4번 노드의 부모 노드인 2번 노드는 leftDepth의 값으로 1을 반환 받고 그 다음으로 maxDepth(root.right)을 실행한다.

4번 노드와 동일하게 5번 노드 역시 2번 노드에 1을 반환한다.

2번 노드에서의 leftDepth와 rightDepth는 각각 1과 1이다.

이제 2번 노드에서의 Math.max(leftDepth, rightDepth) + 1 은 Math.max(1, 1) + 1이므로 2를 반환 한다.

 

1번 노드에서 leftDepth의 값은 2번 노드에서 반환한 2가 될것이고, rightDepth의 값은 3번 노드에서 반환한 1이 될것이다.

이제 1번 노드에서의 Math.max(leftDepth, rightDepth) + 1 은 Math.max(2, 1) + 1이므로 3을 반환 한다.