104. Maximum Depth of Binary Tree (Easy) [Java]

문제

 

생각 방식

DFS - recursion

empty tree가 아니라면 결과는 1 + max(왼쪽, 오른쪽)

왼쪽 depth는 1이고 오른쪽 depth는 2 

그래서 결과는 3이 나온다

 

💻 작성 코드

/**
 * 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;
        }

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

 

return 설명

설명

root node(1)에서 시작

* maxDepth(root.left) -> 왼쪽 subtree(2)로 이동

      * maxDepth(root.left.left) -> 왼쪽 subtree(4)로 이동

      * maxDepth(root.left.left.left) -> node(4)의 왼쪽 subtree에 child가 없기 때문에 null, 그래서 return 0

      * maxDepth(root.left.left.right) -> 똑같음

그래서 왼쪽 subtree(4)의 max depth는 1 + max(0,0) = 1

 

같은 과정을 root node 5, 2, 3에 계속 해준다

 

그럼 마지막에 root node(1)의 max depth는 max(left, right) + 1 = 2 + 1 = 3

결과

Runtime이 계속 이러는데 혹시 어떤 이유인지 아시는 분...?