[leetcode] 111. Minimum Depth of Binary Tree

문제

leetcode.com/problems/minimum-depth-of-binary-tree/

Minimum Depth of Binary Tree - LeetCode

---

풀이

Root 노드에서 Leaf 노드로 가는 가장 짧은 거리를 찾는 문제이다. 문제자체는 BFS만 알면 풀 수 있는 수준이다.BFS(Breadth-first search) 이용해서 풀었다. 

 

 

---

코드

Depth를 계산하다가 Leaf 노드가 없는 경우 값을 반환하면 된다.

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.offer(root);

        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                if (treeNode.left == null && treeNode.right == null) {
                    return depth;
                }

                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
            }
        }
        return depth;
    }

 

 

Discussion를 보니 더 멋진 풀이가 있어 남겨둔다.  더 간단하게도 풀 수 있다.

public int minDepth(TreeNode root) {
  if(root == null) return 0;

  if(root.left == null || root.right == null)
  return 1 + Math.max(minDepth(root.left), minDepth(root.right));

  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
 }

 

 

---

참고

• BFS
• DFS