前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的111题。
问题描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
分析：
回溯法，秒切
func minDepth(root *TreeNode) int {
min := math.MaxInt64
if root == nil {
return 0
}
dfs(root, 1, &min)
return min
}
func dfs(root *TreeNode, depth int, min *int) {
if depth >= *min {
return
}
if root.Left == nil && root.Right == nil{
*min = depth
return
}
if root.Left != nil {
dfs(root.Left, depth+1, min)
}
if root.Right != nil {
dfs(root.Right, depth+1, min)
}
}
别人写的：
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
l, r := minDepth(root.Left), minDepth(root.Right)
if l == 0 || r == 0 {
return l+r+1
}
if l < r {
return l+1
}
return r+1
}
总结：
勤思考。
结语
不管怎么样好好加油。
