Leetcode(111) Minimum Depth of Binary Tree

发表于 | 分类于

Description

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

解法

递归地计算最小深度，需要注意只有一个儿子的节点的节点的高度处理，根据定义，是左儿子深度或右儿子深度加1。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return Math.min(left, right) + 1;
    }
}