leetcode 104 (Maximum Depth of Binary Tree) - Java

문제

이진 트리가 주어지면 최대 깊이를 반환합니다.
이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가장 긴 경로를 따라 있는 노드 수입니다.

예시1

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

예시2

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

제약 조건

트리의 노드 수는 범위 내에 있습니다.[0, 104]
-100 <= Node.val <= 100

풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    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;
    }
}

• 리프 노드까지 가면 leftDepth, leftDepth 는 모두 0이되므로 +1 씩 더해져서 되돌아오며 루트노드로 되돌아 오면 최대 깊이가 반환된다.

3의 왼쪽 노드 9는 왼쪽, 오른쪽 자식 노드 모두 없으므로 깊이가 1이된다.

3의 오른쪽 노드 20은 자식 노드로 15, 7을 가진다.
15, 7 모두 자식 노드가 없으므로 (15,7) 노드에서 깊이 : 1, 20 : 2 가 된다.

9의 깊이는 1이고, 20의 깊이는 2 이므로 더 큰 2가 선택되고 3으로 돌아오며 +1이 되어 최대 깊이는 3이된다.