111 Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree

1. Question

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.

2. Implementation

(1) DFS recursion

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

(2) BFS

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

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

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

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                if (curNode.left == null && curNode.right == null) {
                    return depth;
                }

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return depth;
    }
}

3. Time & Space Complexity

DFS recursion: 时间复杂度: O(h), 空间复杂度: O(h)

BFS:时间复杂度O(n), 空间复杂度: O(w), w为树一层中有最多node的个数