111. 二叉树的最小深度

[yankewei]

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree

[yankewei]

深度优先搜索

深度优先搜索就很简单了，鉴于这种树的性质，经常用递归来求解，对于这个题，我们分别求出左右子树的最小深度就可以了。

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    minD := math.MaxInt32
    if root.Left != nil {
        minD = min(minDepth(root.Left), minD)
    }
    if root.Right != nil {
        minD = min(minDepth(root.Right), minD)
    }
    return minD + 1
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

[yankewei]

广度优先搜索

深度优先搜索有一个问题，就是我必须要递归到底部，去比较左右两个子树的深度。如果我们用广度优先搜索，当找到一个叶子节点，我们直接返回当前深度即可，没有必要再去搜索其它的子树。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    var ret int
    if root == nil {
	return ret
    }
    deQueue := []*TreeNode{root}
    tmpQueue := []*TreeNode{}

    for len(deQueue) != 0 {
	if deQueue[0].Left == nil && deQueue[0].Right == nil {
	    ret++
	    break
	}
	if deQueue[0].Left != nil {
	    tmpQueue = append(tmpQueue, deQueue[0].Left)
	}
	if deQueue[0].Right != nil {
	    tmpQueue = append(tmpQueue, deQueue[0].Right)
	}
	deQueue = deQueue[1:]
	if len(deQueue) == 0 {
	    ret++
	    deQueue = tmpQueue
	    tmpQueue = tmpQueue[len(tmpQueue):]
	}
    }
    return ret
}