111_minimum_depth_of_binary_tree

111. 二叉树的最小深度 简单

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

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

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

示例 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

代码参考：

package main

import "fmt"

func main() {
    tree := &Tree{}
    tree.root = &TreeNode{Val: 1}
    for _, v := range []int{2} {
        tree.BFSInsert(v) // 自己写的破 insert 调试半天  fuck
    }
    fmt.Println(minDepth(tree.root)) // 2
}

func minDepth(root *TreeNode) int {
    return depth(root)
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    lDepth := depth(root.Left)
    rDepth := depth(root.Right)

    if lDepth == 0 { // 左边走到尽头，只能往右边走
        return rDepth + 1
    }
    if rDepth == 0 { // 往左边走
        return lDepth + 1
    }

    return min(lDepth, rDepth) + 1 // 两边都可以走，选最浅的子树
}

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