ChunNote
0%

leetCode-111:Minimum Depth of Binary Tree

发表于 分类于

问题描述

给定一个二叉树，要求找出二叉树的最小高度。题目链接：**点我**

样例输入输出

输入：[1,2,3,4,5]

输出：2

解释：树形状如下

1

/ \

2 3

/\

4 5

输入：[]

输出：0

问题解法

使用递归，算出左子树的最小高度和右子树的最小高度，取其最小值，加一就是本题的答案。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution
{
    public int minDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        
        if (root.left == null && root.right == null)
        {
            return 1;
        }
        
        if (root.left == null)
        {
            return minDepth(root.right) + 1;
        }
        
        if (root.right == null)
        {
            return minDepth(root.left) + 1;
        }
        
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}