Go语言实现二叉树层序遍历求最大宽度及深度

问题目标与结果

给定一棵二叉树，我们需要解决两个具体问题：

1. 找出二叉树中最宽的一层共有多少个节点（最大宽度 maxWidth）。
2. 确定这层节点位于树的第几层（最大宽度所在行 maxInrow）。

示例说明：如下方图片所示的二叉树，其第 3 层拥有 3 个节点，是该树最宽的一层，因此结果为最大宽度 3，所在层级 3。

算法思路与准备

为了按层处理节点并统计数量，最佳策略是使用 广度优先搜索 (BFS)，即基于队列的层序遍历。我们需要维护几个关键变量来控制每层的计数与边界：

• maxWidth：记录历史遇到的最大宽度。
• count：当前正在处理的这一层中已访问的节点数。
• maxInrow：最大宽度对应的层级编号。
• currentRowEndNode：当前层的最后一个节点指针。
• nextRowEndNode：下一层的最后一个节点指针。

由于需要获取左右子节点，我们必须先定义二叉树的节点结构体。在 Go 中，通常使用结构体指向自身类型的指针来表示树。

具体操作步骤

第1步：定义二叉树结构体

首先创建用于存储节点数据及左右孩子引用的结构体。这里以字符串作为节点值以便观察。

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}

第2步：构建测试用例

为了验证算法的正确性，我们先手动构建一个非平衡的二叉树，确保不同层级节点数量有所差异。根节点为 "1"，左子树较深且节点较多。

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)
}

第3步：实现查找最大宽度的核心逻辑

这是算法的核心部分。我们将头节点入队，并通过循环不断从队列头部取出节点进行处理。关键在于如何判断“当前层结束”。

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 {
		treeNode := tempSaveNodeQueue[0]
		tempSaveNodeQueue = tempSaveNodeQueue[1:] // 弹出队列头部
		count++ // 当前层处理节点数加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++ // 层数+1
			
			// 检查是否需要更新最大值
			if maxWidth < count {
				maxInrow = row
				maxWidth = count
			}
			
			// 进入下一层前的重置操作
			currentRowEndNode = nextRowEndNode // 下一行的末尾变成当前的末尾
			count = 0                          // 计数器归零，开始统计下一层
		}
	}
	return
}

第4步：算法原理图解

理解本算法的关键在于对 currentRowEndNode 和 nextRowEndNode 的配合使用。当我们在队列中提取到一个节点时，会将其子节点加入队尾。因为队列是先进先出（FIFO）结构，所有第 N 层的节点一定排在第 N+1 层节点的前面。

当提取出的节点等于 currentRowEndNode 时，意味着同层的所有节点都已处理完毕。此时，我们需要将刚才最后更新的 nextRowEndNode（即新加入的最后那个孩子节点）赋给 currentRowEndNode，从而划定下一层的边界。

注意：为什么在添加子节点时要分别判断 left 和 right 并连续赋值 nextRowEndNode？这是因为并非每个节点都有左右孩子（可能是叶子节点），只有存在的子节点才会被推入队列并成为潜在的该行结束点。

完成判断与总结

运行上述代码后，程序将输出最大宽度及对应层级。通过这种队列结合边界标记的方法，我们无需预先计算树的高度或递归深度，仅需一次层序遍历即可完成任务。

以上就是利用Go语言实现查找二叉树中的最大宽度及深度的详细内容，更多关于Go语言二叉树算法优化的资料请关注本站其它相关文章！