[Dart] 104. Maximum Depth of Binary Tree

1. 문제

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

 

 

 

2. 요구사항

1) 이진 트리의 루트 노드가 주어졌을 때, 이 트리의 최대 깊이를 구한다.

 

 

 

3. 핵심 아이디어

1) 재귀적 접근

각 노드의 왼쪽 노드와 오른쪽 노드의 깊이를 각각 구한 후, 그 중 더 큰 깊이에 1을 더하여 반환한다.

 

 

2) 코드

class Solution {
  int maxDepth(TreeNode? root) {

    // root가 null이면 종료
    if(root ==  null) {
        return 0;
    }

    // 오른쪽 노드의 깊이 구하기
    int rightDepth = maxDepth(root.right);

    // 왼쪽 노드의 깊이 구하기
    int leftDepth = maxDepth(root.left);

    // 오른쪽 노드와 왼쪽 노드 중 가장 큰 값을 구한 후, 1을 더해서 반환
    return 1 + (rightDepth > leftDepth ? rightDepth : leftDepth);
  }
}

 

 

1) 루트 노드(3)에서 시작 -> maxDepth(3) 호출

• leftDepth = maxDepth(9)
• rightDepth = maxDepth(20)

 

 

 

2) 노드 3의 왼쪽 서브트리 탐색 -> maxDepth(9) 호출

 

• 9는 자식 노드가 없음
• maxDepth(null) → 0 (왼쪽)
• maxDepth(null) → 0 (오른쪽)
• maxDepth(9) = 1 + max(0, 0) = 1

 

 

3) 노드 3의 오른쪽 서브트리 탐색 -> maxDepth(20) 호출

 

• leftDepth = maxDepth(15)
• rightDepth = maxDepth(7)

 

 

4) 노드 20의 왼쪽 서브트리 탐색 -> maxDepth(15) 호출

 

• 15는 자식 노드가 없음
• maxDepth(null) → 0 (왼쪽)
• maxDepth(null) → 0 (오른쪽)
• maxDepth(15) = 1 + max(0, 0) = 1

 

 

5) 노드 20의 오른쪽 서브트리 탐색 -> maxDepth(7) 호출

 

• 7은 자식 노드가 없음
• maxDepth(null) → 0 (왼쪽)
• maxDepth(null) → 0 (오른쪽)
• maxDepth(7) = 1 + max(0, 0) = 1

 

 

6) 노드 20에서 최종 계산

 

• leftDepth = 1, rightDepth = 1
• maxDepth(20) = 1 + max(1, 1) = 2

 

 

7) 노드 3에서 최종 계산

 

• leftDepth = 1, rightDepth = 2
• maxDepth(3) = 1 + max(1, 2) = 3