[LeetCode] 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

LeetCode

Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

이진 트리의 root(루트 노드)가 주어졌을 때, 트리의 최대 깊이를 반환하세요.
이진 트리의 최대 깊이는 루트 노드에서 가장 멀리 떨어진 리프 노드(leaf node)까지 이어지는 가장 긴 경로 상의 노드 개수입니다.

 

Example

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

Input: root = [1,null,2]
Output: 2

---

1. 문제 요구사항 분석

트리의 루트 노드부터 가장 멀리 있는 리프(leaf) 노드까지 내려가는 가장 긴 경로의 길이를 구하는 문제

참고사항) The number of nodes in the tree is in the range [0, 10000] => 빈 문자열 유입 가능 !!!

 

2. 접근 전략

😄  DFS(깊이 우선 탐색): 트리 탐색에는 큐(Queue)를 이용한 BFS(너비 우선 탐색) 방식도 가능하지만, 트리의 하위 구조가 반복된다는 특징을 살려 재귀를 활용한 DFS(깊이 우선 탐색) 방식이 코드가 훨씬 간결하고 가독성이 높다고 생각

현재 노드의 왼쪽 자식 트리와 오른쪽 자식 트리의 깊이를 재귀적으로 각각 구한 뒤, 둘 중 더 큰 값에 현재 노드의 깊이인 1을 더해 반환 ➔ 시간복잡도 O(n)

 

// 노드 구조체가 주어졌다고 가정
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        // 예외/경계 조건: 트리가 비어있는 경우 (깊이 0)
        if (root == null) {
            return 0;
        }

        // 왼쪽 서브트리와 오른쪽 서브트리의 깊이를 재귀적으로 탐색
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // 두 서브트리 중 더 깊은 쪽에 현재 노드(+1)를 더해서 반환
        return Math.max(leftDepth, rightDepth) + 1;
    }
}