LeetCode 104(Maximum Depth of Binary Tree, java)

0. 문제

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

Maximum Depth of Binary Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 이 이진트리를 탐색하여 이진트리의 깊이를 반환하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 이전에 풀어본 102번 문제에서 사용한 깊이 단위 탐색을 사용하면 된다.

- que에 들어있는 동일한 깊이의 노드를 for문에서 탐색할 때마다 깊이가 하나씩 증가하는 규칙을 사용하면 된다. 

 

b) 두 번째 접근

- 다른 방식으로는 재귀 함수를 사용하는 방식이 있다.

- 재귀 함수를 사용한 방식은 단말 노드를 시작으로 위로 올라가는 방식으로, 역순의 탐색을 수행한다.

 

- 첫 번째 방식과 두 번째 방식 모두 아래의 코드를 보면서 이해해보자. 

 

3. 정답 코드

a) 깊이 단위 탐색을 이용한 방식

class Solution {
    public int maxDepth(TreeNode root) {
        
        if (root == null) return 0;
        
        Queue<TreeNode> que = new LinkedList<>(); 
        que.offer(root);
        int depth = 0;
        
        while(que.isEmpty() == false) {
        
            depth ++;
            int size = que.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode curn = que.poll();
                
                if(curn.left != null) {
                    que.add(curn.left);
                }
                
                if(curn.right != null) {
                    que.add(curn.right);
                }
            }
        }
        return depth;
    }
}

 

b) 재귀 함수를 이용한 방식

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