111. 二叉树的最小深度、Leetcode的Go实现

🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

⛽️今天的内容是Leetcode 104. 二叉树的最大深度⛽️💻💻💻

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

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

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

示例 1：

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

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

递归(深度搜索)：

分以下三种情况：

1. 当前二叉树左子树为空且右子树不为空时，其最小深度应该是1+右子树的最小深度
2. 当前二叉树右子树为空且左子树不为空时，其最小深度应该是1+左子树的最小深度
3. 当前二叉树左右子树均为空时，返回1。
4. 当前二叉树左右子树均不为空，返回1+min(ld,rd)，

3和4两种情况最小深度的计算可以合并，即1+min(ld,rd)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root==nil{   //和求最大深度不一样，最大深度只需要在当前结点最大值上加1即可
        return 0
    }
    if root.Left==nil&&root.Right!=nil{
        return minDepth(root.Right)+1
    }
    if root.Right==nil&&root.Left!=nil{
        return minDepth(root.Left)+1
    }
    return min(minDepth(root.Left),minDepth(root.Right))+1
}

func min(a,b int) int {
    if a<b {
        return a
    }
    return b
}

层次遍历（广度优先搜索）：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    // 队列实现层次遍历,每加一层，result+1
    if root==nil {
        return 0
    }
    result := 1
    queue := []*TreeNode{root}
    for len(queue)>0 {
        length := len(queue)
        for i:=0;i<length;i++ {
            value:=queue[0]
            queue=queue[1:]
            if value.Left==nil&&value.Right==nil {
                return result
            }
            if value.Left!=nil {
                queue = append(queue,value.Left)
            }
            if value.Right!=nil {
                queue = append(queue,value.Right)
            }
        }
        result++
    }
    return result
}