Star

Leetcode 111. Minimum Depth of Binary Tree

Posted on | In |

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.

Explanation

本题的问题是求根节点到最近的叶节点的距离，叶节点不能是空的。所以考虑的时候，要考虑如果有一边是空的，就只能以另外一边的最短路径长度为准。

比如这个：

返回值为2，而不是1。因为“1”不是叶节点，所以最短路径是从1到2。

Code

DFS1

1
2
3
4
5
6
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    int minLeft = minDepth(root.left); int minRight = minDepth(root.right);
    return 1 + (Math.min(minLeft, minRight) > 0 ? Math.min(minLeft, minRight) : Math.max(minLeft, minRight));
}

DFS2

1
2
3
4
5
6
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left != null && root.right != null) return  1+Math.min(minDepth(root.left), minDepth(root.right));
    if (root.left == null) return 1+minDepth(root.right);
    else return 1+minDepth(root.left);
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int i=0;
    while (queue.peek()!=null) {
        int size = queue.size();
        i ++;
        for (int j=0; j<size; j++) {
            TreeNode cur = queue.peek();
            if (cur.left == null && cur.right == null) return i;
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
            queue.poll();
        }
    }
    return 0;
}