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

知识点掌握了，还需要不断练习才能熟练运用。下面golang学习网给大家带来一个Golang开发实战，手把手教大家学习《利用go语言实现查找二叉树中的最大宽度》，在实现功能的过程中也带大家重新温习相关知识点，温故而知新，回头看看说不定又有不一样的感悟！

介绍

这道题是这样的，有一个二叉树，让求出这颗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 
<h3>代码解读</h3>
<p>这里面的代码大部分的逻辑还是很简单的，</p>
<p>说一下在if判断里面的代码叭，为啥要分别将子节点的<strong>left</strong>、<strong>right</strong>分别赋值给<code>nextRowEndNode</code>呢？</p>
<blockquote><p>因为在一个子节点下面的left和right并不是全都存在的，有的时候会是个空，所以这里要分别赋值</p></blockquote>
<p><code>if currentRowEndNode == treeNode</code>:这一个判断里面，因为如果进入到了这个判断里面就说明到了当前层的最后一个节点了，所以就要把下一层的最后一个节点赋值给当前层的最后一个节点；</p>
<p>因为还有一个要找出最大宽度的一个功能，所以这个maxWidth要和coutn做一个比较如果maxWidth比较小的话就将count赋值给maxWidth，同时将当前的层数赋值给maxInrow；</p>
<p><code>row</code>:而<code>row</code>在这里面所充当的角色是当前是完成第几行的操作</p>
<p><strong>为啥这里要定义一个currentRowEndNode和nextRowEndNode？</strong></p>
<blockquote><p>这种的写法按层来处理，当获取到一个节点的时候，这时我就要拿到他们的子节点，如果现在不获取子节点的话在后面是没有办法获取的，当这一行结束的时候将nextRowEndNode赋值给currentRowEndNode，接下来nextRowEndNode再找下一层的最后一个节点。</p></blockquote>
<p style="text-align:center"><img alt="" src="/uploads/20221228/167222520963ac21b91f4bb.png"></p>
<p>到这里，我们也就讲完了《利用go语言实现查找二叉树中的最大宽度》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！</p>