本文讲解 LeetCode 116 题，要求在完美二叉树中填充每个节点的 next 指针指向右侧相邻节点。介绍了四种解法：BFS 层序遍历、递归连接、迭代 O(1) 空间优化及 DFS 前序遍历。重点分析了如何利用已建立的 next 指针实现空间复杂度 O(1) 的解决方案，并提供了完整的 Go 语言代码实现与测试用例。
给定一个 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
输入：root = []
输出：[]
[0, 2^12 - 1] 范围内-1000 <= node.val <= 1000这是一道二叉树层序遍历的变种问题，核心在于利用已建立的 next 指针进行空间优化。题目要求填充每个节点的 next 指针，使其指向同一层的下一个右侧节点。对于完美二叉树，我们可以利用其结构特性（每层节点数确定、左右子树对称）来实现高效的算法。
给定一个完美二叉树，需要为每个节点建立指向同一层右侧相邻节点的 next 指针。关键点：
利用已建立的 next 指针：
next 连接next 指针连接跨子树的节点next 指针，实现 O(1) 空间复杂度next 应为 NULL| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 方法一：层序遍历（BFS） | O(n) | O(w) | 直观易懂，需要队列存储 |
| 方法二：递归连接 | O(n) | O(h) | 利用递归栈，代码简洁 |
| 方法三：迭代 O(1) 空间 | O(n) | O(1) | 最优解，利用 next 指针 |
| 方法四：DFS 前序遍历 | O(n) | O(h) | 深度优先，先处理父节点 |
说明：
n：节点总数w：树的最大宽度（最后一层节点数）h：树的高度所有方法均为 O(n)：
next 指针被设置一次2^(h-1) 个节点w = 2^(h-1) = O(n/2) = O(n)h = log₂(n+1)O(log n)next 指针遍历O(log n)核心思想：已建立的 next 指针可以作为"横向链表"，用于遍历当前层，从而建立下一层的连接。
// 方法三：迭代 O(1) 空间
func connect3(root *Node) *Node {
if root == nil {
return nil
}
leftmost := root
for leftmost.Left != nil {
// 还有下一层
curr := leftmost
for curr != nil {
// 连接同一父节点的子节点
curr.Left.Next = curr.Right
// 连接跨子树的节点
if curr.Next != nil {
curr.Right.Next = curr.Next.Left
}
curr = curr.Next // 利用 next 指针横向移动
}
leftmost = leftmost.Left // 移动到下一层
}
return root
}
优势：
核心思想：利用父节点的 next 指针，连接不同父节点的子节点。
// 方法二：递归连接
func connect2(root *Node) *Node {
if root == nil {
return nil
}
// 连接同一父节点的子节点
if root.Left != nil {
root.Left.Next = root.Right
}
// 利用父节点的 next 连接跨子树的节点
if root.Right != nil && root.Next != nil {
root.Right.Next = root.Next.Left
}
// 递归处理左右子树
connect2(root.Left)
connect2(root.Right)
return root
}
优势：
核心思想：使用队列逐层处理，为每层节点建立 next 连接。
// 方法一：BFS 层序遍历
func connect1(root *Node) *Node {
if root == nil {
return nil
}
queue := []*Node{root}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
// 连接同层相邻节点
if i < size-1 {
node.Next = queue[0]
}
// 添加子节点到队列
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return root
}
优势：
核心思想：先处理父节点建立连接，再递归处理子节点。
// 方法四：DFS 前序遍历
func connect4(root *Node) *Node {
if root == nil {
return nil
}
// 连接当前节点的子节点
if root.Left != nil {
root.Left.Next = root.Right
if root.Next != nil {
root.Right.Next = root.Next.Left
}
}
// 递归处理左右子树
connect4(root.Left)
connect4(root.Right)
return root
}
优势：
if root == nil {
return nil
}
next 保持为 NULLnext 应为 NULLif i < size-1leftmost.Left != nil 判断是否还有下一层[][][1][1,#][1,2,3][1,#,2,3,#][1,2,3,4,5,6,7][1,#,2,3,#,4,5,6,7,#][1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]错误代码：
// 只连接了同一父节点的子节点
curr.Left.Next = curr.Right
// 忘记了跨子树的连接！
正确做法：
curr.Left.Next = curr.Right
if curr.Next != nil {
curr.Right.Next = curr.Next.Left // 跨子树连接
}
错误代码：
// 错误：在建立连接前就使用 next 指针
for curr != nil {
curr = curr.Next // 此时 next 可能还未建立
curr.Left.Next = curr.Right
}
正确做法：
// 先建立连接，再移动
for curr != nil {
curr.Left.Next = curr.Right
if curr.Next != nil {
curr.Right.Next = curr.Next.Left
}
curr = curr.Next // 建立连接后再移动
}
错误代码：
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
// 错误：队列大小在循环中变化
if len(queue) > 0 {
node.Next = queue[0]
}
// ...
}
正确做法：
for len(queue) > 0 {
size := len(queue) // 固定当前层大小
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if i < size-1 { // 使用索引判断
node.Next = queue[0]
}
// ...
}
}
i 层有 2^(i-1) 个节点next 指针代替队列nil 节点next 指针next 指针prev 指针next 指针可以直接遍历同一层next 指针提供了层序信息本题是二叉树层序遍历的经典变种，核心在于利用已建立的 next 指针实现空间优化。通过四种不同的方法，我们展示了：
关键要点：
next 指针既可以存储结果，也可以作为遍历工具掌握本题有助于理解树形结构的层序遍历和空间优化技巧，为后续更复杂的树形问题打下基础。
package main
import "fmt"
// =========================== Node 定义 ===========================
type Node struct {
Val int
Left *Node
Right *Node
Next *Node
}
// =========================== 方法一：BFS 层序遍历 ===========================
// 时间复杂度：O(n)，空间复杂度：O(w)，w 为树的最大宽度
func connect1(root *Node) *Node {
if root == nil {
return nil
}
queue := []*Node{root}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
// 连接同层相邻节点（不是最后一个节点）
if i < size-1 {
node.Next = queue[0]
}
// 添加子节点到队列
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return root
}
// =========================== 方法二：递归连接 ===========================
// 时间复杂度：O(n)，空间复杂度：O(h)，h 为树的高度
func connect2(root *Node) *Node {
if root == nil {
return nil
}
// 连接同一父节点的子节点
if root.Left != nil {
root.Left.Next = root.Right
}
// 利用父节点的 next 连接跨子树的节点
if root.Right != nil && root.Next != nil {
root.Right.Next = root.Next.Left
}
// 递归处理左右子树
connect2(root.Left)
connect2(root.Right)
return root
}
// =========================== 方法三：迭代 O(1) 空间（最优解） ===========================
// 时间复杂度：O(n)，空间复杂度：O(1)
func connect3(root *Node) *Node {
if root == nil {
return nil
}
// leftmost 指向每层最左边的节点
leftmost := root
// 逐层处理，直到叶子节点层
for leftmost.Left != nil {
// 当前层的当前节点
curr := leftmost
// 遍历当前层的所有节点
for curr != nil {
// 连接同一父节点的子节点
curr.Left.Next = curr.Right
// 连接跨子树的节点
if curr.Next != nil {
curr.Right.Next = curr.Next.Left
}
// 移动到当前层的下一个节点
curr = curr.Next
}
// 移动到下一层
leftmost = leftmost.Left
}
return root
}
// =========================== 方法四：DFS 前序遍历 ===========================
// 时间复杂度：O(n)，空间复杂度：O(h)，h 为树的高度
func connect4(root *Node) *Node {
if root == nil {
return nil
}
// 连接当前节点的子节点
if root.Left != nil {
root.Left.Next = root.Right
// 如果当前节点有 next，连接跨子树的节点
if root.Next != nil {
root.Right.Next = root.Next.Left
}
}
// 递归处理左右子树
connect4(root.Left)
connect4(root.Right)
return root
}
// =========================== 工具函数：从数组构建完美二叉树 ===========================
func arrayToTreeLevelOrder(arr []interface{}) *Node {
if len(arr) == 0 || arr[0] == nil {
return nil
}
root := &Node{Val: arr[0].(int)}
queue := []*Node{root}
i := 1
for i < len(arr) && len(queue) > 0 {
node := queue[0]
queue = queue[1:]
// 左子节点
if i < len(arr) && arr[i] != nil {
left := &Node{Val: arr[i].(int)}
node.Left = left
queue = append(queue, left)
}
i++
// 右子节点
if i < len(arr) && arr[i] != nil {
right := &Node{Val: arr[i].(int)}
node.Right = right
queue = append(queue, right)
}
i++
}
return root
}
// =========================== 工具函数：验证 next 指针连接 ===========================
func validateNextPointers(root *Node) []string {
if root == nil {
return []string{}
}
var result []string
leftmost := root
// 逐层遍历
for leftmost != nil {
curr := leftmost
level := []int{}
// 通过 next 指针遍历当前层
for curr != nil {
level = append(level, curr.Val)
curr = curr.Next
}
// 格式化输出
levelStr := ""
for i, v := range level {
if i > 0 {
levelStr += " -> "
}
levelStr += fmt.Sprintf("%d", v)
}
result = append(result, levelStr)
// 移动到下一层
leftmost = leftmost.Left
}
return result
}
// =========================== 工具函数：按层序输出（带 next 信息） ===========================
func levelOrderWithNext(root *Node) []interface{} {
if root == nil {
return []interface{}{}
}
var result []interface{}
leftmost := root
for leftmost != nil {
curr := leftmost
for curr != nil {
result = append(result, curr.Val)
curr = curr.Next
}
result = append(result, "#") // 层分隔符
leftmost = leftmost.Left
}
return result
}
// =========================== 工具函数：比较结果 ===========================
func equal(a, b []interface{}) bool {
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
// =========================== 测试 ===========================
func main() {
fmt.Println("=== LeetCode 116: 填充每个节点的下一个右侧节点指针 ===\n")
testCases := []struct {
name string
root *Node
expected []interface{}
}{
{name: "空树", root: arrayToTreeLevelOrder([]interface{}{}), expected: []interface{}{}},
{name: "单节点", root: arrayToTreeLevelOrder([]interface{}{1}), expected: []interface{}{1, "#"}},
{name: "两层树", root: arrayToTreeLevelOrder([]interface{}{1, 2, 3}), expected: []interface{}{1, "#", 2, 3, "#"}},
{name: "三层完美二叉树", root: arrayToTreeLevelOrder([]interface{}{1, 2, 3, 4, 5, 6, 7}), expected: []interface{}{1, "#", 2, 3, "#", 4, 5, 6, 7, "#"}},
{name: "四层完美二叉树", root: arrayToTreeLevelOrder([]interface{}{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}), expected: []interface{}{1, "#", 2, 3, "#", 4, 5, 6, 7, "#", 8, 9, 10, 11, 12, 13, 14, 15, "#"}},
}
methods := []struct {
name string
fn func(*Node) *Node
}{
{"方法一：BFS 层序遍历", connect1},
{"方法二：递归连接", connect2},
{"方法三：迭代 O(1) 空间", connect3},
{"方法四：DFS 前序遍历", connect4},
}
allPassed := true
for _, method := range methods {
fmt.Printf("--- %s ---\n", method.name)
passed := 0
for i, tc := range testCases {
// 重新构建树（因为会修改原树）
testRoot := arrayToTreeLevelOrder(getTreeArray(tc.name))
result := method.fn(testRoot)
got := levelOrderWithNext(result)
if equal(got, tc.expected) {
fmt.Printf(" Test %d: ✓ PASSED\n", i+1)
passed++
} else {
fmt.Printf(" Test %d: ✗ FAILED\n", i+1)
fmt.Printf(" 输入：%v\n", getTreeArray(tc.name))
fmt.Printf(" 期望：%v\n", tc.expected)
fmt.Printf(" 得到：%v\n", got)
allPassed = false
}
}
fmt.Printf("通过率：%d/%d\n\n", passed, len(testCases))
}
if allPassed {
fmt.Println("🎉 所有测试通过！")
} else {
fmt.Println("❌ 部分测试失败")
}
}
// 辅助函数：根据测试用例名称获取树数组
func getTreeArray(name string) []interface{} {
switch name {
case "空树":
return []interface{}{}
case "单节点":
return []interface{}{1}
case "两层树":
return []interface{}{1, 2, 3}
case "三层完美二叉树":
return []interface{}{1, 2, 3, 4, 5, 6, 7}
case "四层完美二叉树":
return []interface{}{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
default:
return []interface{}{}
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online