[Java][LeetCode][Blind75] 104. Maximum Depth of Binary Tree | EASY | Recursion

오랜만에 트리 문제 풀기! +ㅁ+

 

문제 / 예제 / 제한조건 :

알고보니 예전에도 푼 적이 있던 문제였다!

예전이랑 비슷하지만 다른 방식으로 풀어서 보는 재미가 있는 느낌쓰~

 

# 풀이 1

Solution에서 주는 함수 외에 

count를 인자로 갖는 새로운 함수를 생성해서 해당 함수로 계산하는 방식

node가 null 이 될 때까지 count + 1 를 해주면서 깊이를 세준다.

노드에는 왼쪽 오른쪽이 있는데, 둘 중에 깊이가 더 깊은 수로 count를 해줘야 하기 때문에 Math.max 를 사용

/**
 * 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) {
        return CalculateDepth(root, 0);
    }
    
    private int CalculateDepth(TreeNode node, int count) {
        if(node == null) return count;

        return Math.max(CalculateDepth(node.left, count+1), CalculateDepth(node.right, count+1));
    }
}

Time Complexity : O(n)
Space Complexity : O(n) in the worst case / O(log n) in balanced trees.

# 풀이 2

예전에 풀었던 방식은 

count라는 인자를 따로 쓰지 않고 바로 리턴을 해주는 방식으로 했었다.

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

Time Complexity : O(n)
Space Complexity : O(n) in the worst case / O(log n) in balanced trees.

 

쉽게 푼 문제!

이제 슬슬 Tree 에 대한 감이 잡히고 있는 것인가~.~