[LeetCode] Maximum Depth of Binary Tree

leetcode.com/explore/featured/card/top-interview-questions-easy/94/trees/555/

Explore - LeetCode

root 가 null 이면 return 0 하고, leaf 노드이면 1을 리턴하면 되지 않을까..해서

어쨋든 루트 노드에 닿아야 한다고 생각했던 나는 루트 노드의 개수를 구해버림

 

1)

First try : tried to reach tree's leaf node
Result : number of leaf nodes

class Solution{
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return maxDepth(root.left) + maxDepth(root.right);
    }
}

 

2) 

Second try : came up with Math.max()

Result : didn't add root node (+1)

루트 노드의 개수를 더하는 게 아니라, 왼쪽 노드의 깊이와 오른쪽 노드의 깊이 중 더 큰 깊이를 구해야 한다고 생각해서 둘 중에 더 큰 수를 구하는 Math.max() 함수를 떠올렸다.

class Solution{
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

이렇게 하니 루트 노드를 더하지 않은 값이 출력되어서 +1을 해야한다고 생각

근데 중간에 틀어져서 여기까지 못왔다 답을 앞에 두고 !!! 메서드를 새로 만들어야 하나 고민했다.

왼쪽 루트와 오른쪽 루트를 따로 깊이를 구해서 둘 중 큰 수를 리턴해야 겠다는 생각과.. 여러 고민이 들어서

정답이 코 앞인데 돌아가기ㅋㅋㅋ 다 맞춰놓고 돌아간 나는 바보 ... 🤦‍♀️

 

이렇게만 냈어도 통과였을텐데, 하다하다 안되어서 Discuss를 열람했다.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

여기서 중간 if문이 없어도 메서드가 동작한다는 사실을 알았다.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Runtime: 0 ms
Memory Usage: 39.2 MB

 

Maximum Depth of Binary Tree