111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

注意：

1. 如果树只有一个根结点，minDepth = 1.
2. 如果树只有一个根结点和一个子节点，比如[1,null,2]，minDepth = 2.

Solution 1: Recursive, preorder O(n); O(h)

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return left == 0 || right == 0 ? left + right + 1 : Math.min(left, right) + 1;
    }

Follow Up:

1.问我树非常如果不平衡（左边10，右边1那种），有没有更好的解法。

Solution: BFS O(n); O(w)

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int min = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) { //level order模板
                TreeNode cur = queue.poll();
                if (cur.left == null && cur.right == null) {
                    return min;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            min++;
        }
        return min;
    }