二叉树的最小深度

[编程题]二叉树的最小深度

热度指数：3670 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗节点数为N的二叉树，求其最小深度。最小深度是指树的根节点到最近叶子节点的最短路径上节点的数量。

（注：叶子节点是指没有子节点的节点。）

数据范围：

0<=N<=6000

0<=val<=100

你能使用时间复杂度为O(N)，空间复杂度为O(logN)的解法通过本题吗？

例如当输入{1,2,3,4,5}时，对应的二叉树如下图所示：

可以看出离根节点最近的叶子节点是节点值为3的节点，所以对应的输出为2。

示例1

输入

{1,2,3,4,5}

输出

示例2

输入

{1,#,2,#,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

小谷围做题家

package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
*/
func run( root *TreeNode ) int {
    if root==nil{
        return 0
    }
    ans:=1
    q:=[]*TreeNode{root}
    for len(q)>0{
        new_q:=[]*TreeNode{}
        for _,qi:=range q{
            if qi.Left==nil&&qi.Right==nil{
                return ans
            }
            if qi.Left!=nil{
                new_q=append(new_q,qi.Left)
            }
            if qi.Right!=nil{
                new_q=append(new_q,qi.Right)
            }
        }
        ans++
        q=new_q
    }
    return ans
}

发表于 2023-03-08 23:58:04 回复(0)

王飞-6

dfs

func run( root *TreeNode ) int {
    if root == nil {return 0}
    if root.Left == nil && root.Right != nil {
        return 1 + run(root.Right);
    }
    if root.Right == nil && root.Left != nil {
        return 1 + run(root.Left);
    }
    return min(run(root.Left), run(root.Right)) + 1;
}
func min(a, b int) int {
    if a < b {
        return a;
    }
    return b;
}

发表于 2021-11-26 16:22:04 回复(0)