LeetCode-111.二叉树的最小深度

二叉树#

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

1
输入：root = [3,9,20,null,null,15,7]
2
输出：2

示例 2：

1
输入：root

自己的解法

思路：这题与二叉树的最小深度稍有不同，求最小时会面临一个问题：如果一颗树是“偏瘫”的（比如只有左边的，没有右边的），直接用 min(left, right)，右边的空指针会返回深度 0，导致整棵树算出来的最小深度是 1。

所以，我们需要if root.Left == nil && root.Right != nil { ... } 和 if root.Right == nil && root.Left != nil { ... } 去除这些错误

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func minDepth(root *TreeNode) int {
10
    if root == nil {
11
        return 0
12
    }
13

14
    if root.Left == nil && root.Right != nil {
15
        return minDepth(root.Right) + 1
16
    }
17

18
    if root.Right == nil && root.Left != nil {
19
        return minDepth(root.Left) + 1
20
    }
21

22
    return min(minDepth(root.Left), minDepth(root.Right)) + 1
23
}