104. Maximum Depth of Binary Tree

최대 깊이를 구하시오. 그림에선 3이 깊이 1이고, 9랑 20이 깊이 2, 15랑 7이 깊이 3이므로 깊이 3을 리턴하면 됨.

 

 

[내가 작성한 코드]

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        int depth = 0;

        if (root == null) {
            return depth;
        }

        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                TreeNode node = q.poll();
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }

            depth++;
        }

        return depth;
    }
}

이제 막 BFS 개념 잡고 처음 푼 문제라서 그냥 BFS식으로 풀었습니다.

처음 들어가서 q.size()로 현재 depth에 있는 요소들의 수를 파악한 후, 그 요소만큼만 반복하면 depth가 증가하는 식입니다.

 

 

리트코드 최다 추천 답안

Simple solution using Java - LeetCode Discuss

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

진짜 기발하다고 생각한 코드.
재귀식으로 매번 root를 바꾸는 방식.
마지막엔 1+Math.max(left의 최대 깊이, right의 최대깊이)가 돼서, 둘 중 최대 깊이를 반환하면
1+root의 자식 요소의 최대 깊이가 되므로, 최대깊이를 구할 수 있습니다. (1을 더한 건 맨처음 root의 depth인 1을 더해준 것)
굉장히 코드가 짧고 잘 짠 코드 같음.