go语言算法题解二叉树的最小深度

目录
  • 题目：
    • 说明：
  • 解法：

题目：

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

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

说明：

叶子节点是指没有子节点的节点。

解法：

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	minDepth := math.MaxInt64
	var dfs func(node *TreeNode, depth int)
	dfs = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		depth ++
		if node.Left == nil && node.Right == nil {
			if depth < minDepth {
				minDepth = depth
			}
		}
		dfs(node.Left, depth)
		dfs(node.Right, depth)
	}
	dfs(root, 0)
	return minDepth
}

以上就是go语言算法题解二叉树的最小深度的详细内容，更多关于go 二叉树最小深度的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go 数据结构之二叉树详情

    Go 数据结构之二叉树详情

    目录 Go 语言实现二叉树 定义二叉树的结构 二叉树遍历 创建二叉树 插入值 测试 前言: 树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同. 而在其中最常用的树之一是二叉树. 二叉树是一棵树,其中每个节点最多可以有两个孩子. 一个孩子被识别为左孩子,另一个孩子被识别为右孩子. 二叉树是一种数据结构,在每个节点下面最多存在两个其他节点.即一个节点要么连接至一个.两个节点或不连接其他节点. 树形结构的深度(也被称作高度)则被定义为根节点为根节点

  • 利用go语言判断是否是完全二叉树

    利用go语言判断是否是完全二叉树

    目录 一.什么是完全二叉树? 二.流程 三.代码 1.树节点 2.测试代码 3.判断树是否为完全二叉树代码 4.代码解读 5.运行结果 一.什么是完全二叉树? 先看如下这一张图: 这个一颗二叉树,如何区分该树是不是完全二叉树呢? 当一个节点存在右子节点但是不存在左子节点这颗树视为非完全二叉树 当一个节点的左子节点存在但是右子节点不存在视为完全二叉树 如果没有子节点,那也是要在左侧开始到右侧依次没有子节点才视为完全二叉树,就像上图2中 而上面第一张图这颗二叉树很明显是一颗非完全二叉树,因为在第三层

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • 利用go语言实现查找二叉树中的最大宽度

    利用go语言实现查找二叉树中的最大宽度

    目录 介绍 流程 代码 二叉树结构体 测试代码 查找二叉树最大宽度的代码 代码解读 介绍 这道题是这样的,有一个二叉树,让求出这颗Bt树里面最大的宽度是有几个节点,同时还要求出最大宽度的这些节点在第几层? 比如:下面这颗树,它每层最大的宽度是3,所在的层数是在第3层 流程 这个题主要是使用队列的方式来存储需要遍历的节点 同时还需要几个变量来存储最大的宽度(maxWidth).每层有几个节点(count).最大宽度所在的层(maxInrow).当前层最后一个节点(currentRowEndNode

  • 详解Go语言如何实现二叉树遍历

    详解Go语言如何实现二叉树遍历

    目录 1. 二叉树的定义 2. 前序遍历 3. 中序遍历 4. 后序遍历 1. 二叉树的定义 二叉树需满足的条件 ① 本身是有序树 ② 树中包含的各个节点的长度不能超过2,即只能是0.1或者2 2. 前序遍历 前序遍历二叉树的顺序:根——>左——>右 package main import "fmt" //定义结构体 type Student struct { Name string Age int Score float32 left *Student //左子树指针 r

  • go语言实现二叉树的序例化与反序列化

    go语言实现二叉树的序例化与反序列化

    目录 二叉树的反序列化 反序列化 解题思路 TreeNode结构体 反序列化方法 代码解读 二叉树的序列化 介绍 解题思路 代码 代码解读 运行结果 二叉树的反序列化 反序列化 树的反序列化故名知意就是将一个序列化成字符串或者其它形式的数据重新的生成一颗二叉树,如下这颗二叉树将它序列化成字符串后的结果[5,4,null,null,3,2,1],而现在要做的是要将这个字符串重新的生成一颗二叉树(生成下面这颗树,因为这个字符串就是通过这颗树序列化来的). 解题思路 首先,应该先拿到一个序列化后数据,

  • go语言算法题解二叉树的最小深度

    目录 题目: 说明: 解法: 题目: 给定一个二叉树,找出其最小深度. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量. 说明: 叶子节点是指没有子节点的节点. 解法: func minDepth(root *TreeNode) int { if root == nil { return 0 } minDepth := math.MaxInt64 var dfs func(node *TreeNode, depth int) dfs = func(node *TreeNode, dept

  • Python实现二叉树的最小深度的两种方法

    找到给定二叉树的最小深度 最小深度是从根节点到最近叶子节点的最短路径上的节点数量 注意:叶子节点没有子树 Example: Given binary tree [3,9,20,null,null,15,7], 3    / \   9  20     /  \    15   7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该二叉树的最小深度 def minDepth(self, root):

  • C++实现LeetCode(111.二叉树的最小深度)

    [LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度 Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no child

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言算法打卡回文串验证算法题解

    C语言算法打卡回文串验证算法题解

    目录 概念 Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 点杀回文排列 点杀回文验证(有效性) 对撞指针 概念 所谓回文串,就是字符串反转以后和原串相同,如 abba 和 lippil.对于回文串还是比较容易去验证的,从字符数组的两端开始向中间靠拢去验证字符是否相等,但这里是否需要考虑字符数组长度的奇偶性呢?其实是不用的,下面一起来看看: Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 (1,2题是一样的,合并讲解吧) 点杀回文排列 先讲回文排列吧,

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • C语言实现线索二叉树的定义与遍历示例

    C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

  • C语言 链式二叉树结构详解原理

    C语言 链式二叉树结构详解原理

    目录 前言 二叉树节点声明 二叉树的遍历 构建二叉树 1.前序遍历 2.中序遍历 3.后序遍历 二叉树节点的个数 二叉树叶子节点的个数 二叉树第K层节点个数 二叉树的高度/深度 二叉树查找值为x的节点 整体代码 前言 二叉树不同于顺序表,一颗普通的二叉树是没有增删改查的意义.普通的二叉树用来存储数据是不方便的.但是二叉树的一些基本实现结构,例如前序遍历,中序遍历...等等都是对我们学习更深层次的二叉树打下夯实的基础. 二叉树节点声明 typedef char BTDataType; typede

  • C语言深入浅出解析二叉树

    C语言深入浅出解析二叉树

    目录 树概念及结构 相关概念 树的表示 树在实际中的运用(表示文件系统的目录树结构) 二叉树概念及结构 概念 需要注意的特殊二叉树 二叉树的性质 二叉树的存储结构 顺序存储 链式存储 总结 树概念及结构 树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 注意: 有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.

随机推荐