利用go语言实现查找二叉树中的最大宽度
作者:??呆呆灿???? 时间:2024-05-28 15:22:31
介绍
这道题是这样的,有一个二叉树,让求出这颗Bt树里面最大的宽度是有几个节点,同时还要求出最大宽度的这些节点在第几层?
比如:下面这颗树,它每层最大的宽度是3,所在的层数是在第3层
流程
这个题主要是使用队列的方式来存储需要遍历的节点
同时还需要几个变量来存储最大的宽度(maxWidth)、每层有几个节点(count)、最大宽度所在的层(maxInrow)、当前层最后一个节点(currentRowEndNode)、下一层最后一个节点(nextRowEndNode)
程序的一开始,便将二叉树的头节点加入到队列里面,同时将这个节点赋值给下一层最后一个节点因当根节点只有一个节点,同时也将当前行的最后一个节点赋值为这个节点
通过循环来对这个队列进行遍历,当进入循环后就认为走到了一个节点,count就要加1
将队列里面的节点元素开始弹出,如果它的子节点存在就将子节点赋值给nextRowEndNode,先赋值左再赋值右(因为先处理的是左子节点),同时将这俩个节点加入到队列里面(如果它们存在的话)
还要对当前的节点进行一个判断,判断当前的节点是不是到了当前行的最后一个节点,如果是的话,就代表当前行的数据已经处理完成,就要把nextRowEndNode赋值给currentRowEndNode,count置0
进行下一波循环
代码
二叉树结构体
type TreeNode struct {
val string
left *TreeNode
right *TreeNode
}
测试代码
func main() {
sNode := &TreeNode{val: "1"}
sNode.left = &TreeNode{val: "2"}
sNode.right = &TreeNode{val: "3"}
sNode.left.left = &TreeNode{val: "4"}
sNode.left.right = &TreeNode{val: "5"}
sNode.right.left = &TreeNode{val: "6"}
sNode.left.left.left = &TreeNode{val: "7"}
sNode.left.left.right = &TreeNode{val: "8"}
sNode.left.right.left = &TreeNode{val: "9"}
sNode.left.right.right = &TreeNode{val: "10"}
sNode.right.left.left = &TreeNode{val: "11"}
maxW, row := findBtMaxWidth(sNode)
fmt.Printf("最大宽度: %v;在第 %v层", maxW, row)
}
查找二叉树最大宽度的代码
func findBtMaxWidth(bt *TreeNode) (maxWidth int, maxInrow int) {
row := 0
//临时保存节点的队列
var tempSaveNodeQueue []*TreeNode
//保存宽度
count := 1
var currentRowEndNode *TreeNode
var nextRowEndNode *TreeNode
if bt != nil {
nextRowEndNode = bt
currentRowEndNode = nextRowEndNode
tempSaveNodeQueue = append(tempSaveNodeQueue, bt)
}
for len(tempSaveNodeQueue) != 0 {
count++
treeNode := tempSaveNodeQueue[0]
tempSaveNodeQueue = tempSaveNodeQueue[1:]
if treeNode.left != nil {
nextRowEndNode = treeNode.left
tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.left)
}
if treeNode.right != nil {
nextRowEndNode = treeNode.right
tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.right)
}
if currentRowEndNode == treeNode {
row++
currentRowEndNode = nextRowEndNode
if maxWidth < count {
maxInrow = row
maxWidth = count
}
count = 0
}
}
return
}
代码解读
这里面的代码大部分的逻辑还是很简单的,
说一下在if判断里面的代码叭,为啥要分别将子节点的left、right分别赋值给nextRowEndNode
呢?
因为在一个子节点下面的left和right并不是全都存在的,有的时候会是个空,所以这里要分别赋值
if currentRowEndNode == treeNode
:这一个判断里面,因为如果进入到了这个判断里面就说明到了当前层的最后一个节点了,所以就要把下一层的最后一个节点赋值给当前层的最后一个节点;
因为还有一个要找出最大宽度的一个功能,所以这个maxWidth要和coutn做一个比较如果maxWidth比较小的话就将count赋值给maxWidth,同时将当前的层数赋值给maxInrow;
row
:而row
在这里面所充当的角色是当前是完成第几行的操作
为啥这里要定义一个currentRowEndNode和nextRowEndNode?
这种的写法按层来处理,当获取到一个节点的时候,这时我就要拿到他们的子节点,如果现在不获取子节点的话在后面是没有办法获取的,当这一行结束的时候将nextRowEndNode赋值给currentRowEndNode,接下来nextRowEndNode再找下一层的最后一个节点。
来源:https://juejin.cn/post/6981023626619437070
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
DB2和 Oracle的并发控制(锁)的比较
Python Matplotlib通过plt.subplots创建子绘图
![](https://img.aspxhome.com/file/2023/5/98905_0s.png)
python GUI库图形界面开发之PyQt5状态栏控件QStatusBar详细使用方法实例
![](https://img.aspxhome.com/file/2023/8/121898_0s.png)
javascript设置和获取cookie的方法实例详解
浅析MySQL数据库授权原则
使用 tke-autoscaling-placeholder 实现秒级弹性伸缩的方法
![](https://img.aspxhome.com/file/2023/5/112085_0s.png)
Python3.5内置模块之time与datetime模块用法实例分析
![](https://img.aspxhome.com/file/2023/1/63231_0s.png)
从console.log说起(console.log详细介绍)
![](https://img.aspxhome.com/file/2023/0/117500_0s.jpg)
关于web标准的思考
利用vue+elementUI实现部分引入组件的方法详解
使用python将图片按标签分入不同文件夹的方法
![](https://img.aspxhome.com/file/2023/6/118716_0s.jpg)
python pandas中对Series数据进行轴向连接的实例
解读SQL语句中要不要加单引号的问题
![](https://img.aspxhome.com/file/2023/4/120854_0s.png)
bootstrap-table formatter 使用vue组件的方法
Centos6.5在线安装mysql 8.0详细教程
pandas 使用apply同时处理两列数据的方法
Python实现PDF转MP3的示例代码
![](https://img.aspxhome.com/file/2023/2/95152_0s.png)
Python 中的lambda匿名函数和三元运算符
python实现桌面托盘气泡提示
goFrame的队列gqueue对比channel使用详解
![](https://img.aspxhome.com/file/2023/1/134391_0s.jpg)