본문 바로가기

알고리즘 문제풀이/LeetCode

[LeetCode 104] Maximum Depth of Binary Tree with JAVA

leetcode.com/problems/maximum-depth-of-binary-tree/

 

Maximum Depth of Binary Tree - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: root = [] Output: 0

Example 4:

Input: root = [0] Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [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;
        else return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

1. 어려웠던 점:

- 처음에는 root.left, root.right 가 각각 null일 때, 둘 다 null 일 때, 따로따로 확인했지만, 첫 TreeNode가 null이 올 수 있다는 제약 사항을 확인하지 못했다. 그 후, root가 null일 때로 재귀문을 바꾸니 훨씬 깔끔하게 리팩토링 되었다.

2. 알게된 점:

- 그래프 이론 복습 (depth)

- 제약 사항 확인을 잘하자.

- 재귀문 복습.

 

3. 알고리즘 풀이:

root가 null이면 깊이는 0이다.

root의 깊이는 left node와 right node의 깊이 중, 더 큰 값에 1을 더한 값이다.