[Easy] 104. Maximum Depth of Binary Tree

Leetcode 104번 문제는 주어진 binary tree의 최대 깊이 (Maximum depth)를 구하는 문제이다. 

 

#풀이

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

이 문제는 recursion를 통해 쉽게 풀수 있다. 왼쪽 tree의 깊이를 구하고 오른쪽 트리의 깊이와 비교해 더 큰 값을 return하는 식으로 풀수 있다. 위의 코드를 간략하면 아래처럼 된다.

class Solution {
public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
 }
 //한줄로도 축약가능
 //return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;

또한 이 문제는 recursion말고도 stack(DFS) 이나 queue (BFS)를 사용해 반복적 (iteratively)으로도 풀수있다. 

//Stack을 사용한 DFS 풀이
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int max = 1;
        
        Stack<TreeNode> nodes = new Stack<>();
        Stack<Integer> depths = new Stack<>();
        
        nodes.push(root);
        depths.push(1);
        
        while (!nodes.empty()) {
            TreeNode curr = nodes.pop();
            int depth = depths.pop();
            
            if (curr.left == null && curr.right == null) {
                max = Math.max(max, depth);
            } 
            
            if (curr.right != null) {
                nodes.push(curr.right);
                depths.push(depth + 1);
            } 
            if (curr.left != null) {
                nodes.push(curr.left);
                depths.push(depth + 1);
            }
        }
        
        return max;
        
    }
}

 

//Queue를 사용한 BFS풀이
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int depth = 0;
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            depth++;
            while (size-- > 0) {
                TreeNode node = nodes.poll();
                if (node.left != null) nodes.offer(node.left);
                if (node.right != null) nodes.offer(node.right);
            }
        }
        return depth;
    }
}