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

第利用go语言实现查找二叉树中的最大宽度目录介绍流程代码二叉树结构体测试代码查找二叉树最大宽度的代码代码解读

介绍

这道题是这样的，有一个二叉树，让求出这颗Bt树里面最大的宽度是有几个节点，同时还要求出最大宽度的这些节点在第几层？

比如:下面这颗树，它每层最大的宽度是3，所在的层数是在第3层

流程

这个题主要是使用队列的方式来存储需要遍历的节点同时还需要几个变量来存储最大的宽度(maxWidth)、每层有几个节点(count)、最大宽度所在的层(maxInrow)、当前层最后一个节点(currentRowEndNode)、下一层最后一个节点(nextRowEndNode)程序的一开始，便将二叉树的头节点加入到队列里面，同时将这个节点赋值给下一层最后一个节点因当根节点只有一个节点，同时也将当前行的最后一个节点赋值为这个节点通过循环来对这个队列进行遍历，当进入循环后就认为走到了一个节点，count就要加1将队列里面的节点元素开始弹出，如果它的子节点存在就将子节点赋值给nextRowEndNode,先赋值左再赋值右(因为先处理的是左子节点)，同时将这俩个节点加入到队列里面(如果它们存在的话)还要对当前的节点进行一个判断，判断当前的节点是不是到了当前行的最后一个节点，如果是的话，就代表当前行的数据已经处理完成，就要把nextRowEndNode赋值给currentRowEndNode，count置0进行下一波循环

代码

二叉树结构体

typeTreeNodestruct{

valstring

left*TreeNode

right*TreeNode

}

测试代码

funcmain(){

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)

}

查找二叉树最大宽度的代码

funcfindBtMaxWidth(bt*TreeNode)(maxWidthint,maxInrowint){

row:=0

//临时保存节点的队列

vartempSaveNodeQueue[]*TreeNode

//保存宽度

count:=1

varcurrentRowEndNode*TreeNode

varnextRowEndNode*TreeNode

ifbt!=nil{

nextRowEndNode=bt

currentRowEndNode=nextRowEndNode

tempSaveNodeQueue=append(tempSaveNodeQueue,bt)

forlen(tempSaveNodeQueue)!=0{

count++

treeNode:=tempSaveNodeQueue[0]

tempSaveNodeQueue=tempSaveNodeQueue[1:]

iftreeNode.left!=nil{

nextRowEndNode=treeNode.left

tempSaveNodeQueue=append(tempSaveNodeQueue,treeNode.left)

iftreeNode.right!=nil{

nextRowEndNode=treeNode.right

tempSaveNodeQueue=append(tempSaveNodeQueue,treeNode.right)

ifcurrentRowEndNode==treeNode{

row++

currentRowEndNode=nextRowEndNode

ifmaxWidthcount{

maxInrow=row

maxWidth=count

count=0

return

}

代码解读

这里面的代码大部分的逻辑还是很简单的，

说一下在if判断里面的代码叭，为啥要分别将子节点的left、right分别赋值给nextRowEndNode呢？

因为在一个子节点下面的left和right并不是全都存在的，有的时候会是个空，所以这里要分别赋值

ifcurrentRowEndNode==treeNode:这一个判断里面，因为如果进入到了这个判断里面就说明到了当前层的最后一个节点了，所以就要把下一层的最后一个节点赋值给当前层的最后一个节点；

因为还有一个要找出最大宽度的一个功能，所以这个maxWidth要和coutn做一个比较如果maxWidth比较小的话就将count赋值给maxWidth，同时将当前的层数赋值给maxInrow；

row:而row在这里面所充当的角色是当前是完成第几行的操作

为啥这里要定义一个currentRowEndNode和nextRowEndNode？