企业官网建设流程全解析

LeetCode 116 题要求填充每个节点的
“next” 指针，使其指向右侧相邻的节点。由于题目给定的是完美二叉树，我们可以利用这一特性，在 O(1) 额外空间内完成（递归解法的栈空间不计入额外空间复杂度）。

以下提供两种 Python3 实现方式：

方法一：利用已建立的 next 指针（迭代，O(1) 空间，推荐）

思路：

从根节点开始，把每一层看作一个链表。通过上一层已经连接好的
“next” 指针，来连接当前层的子节点。

“”"

Definition for a Node.

class Node:
definit(self, val: int = 0, left: ‘Node’ = None, right: ‘Node’ = None, next: ‘Node’ = None):
self.val = val
self.left = left
self.right = right
self.next = next
“”"

class Solution:
def connect(self, root: ‘Node’) -> ‘Node’:
if not root:
return None

# leftmost 指向每一层的最左节点 leftmost = root # 只要当前层不是叶子层（即还有下一层） while leftmost.left: # head 用于遍历当前层的节点 head = leftmost while head: # 1. 同一个父节点的左孩子 -> 右孩子 head.left.next = head.right # 2. 不同父节点之间：当前节点的右孩子 -> 下一个节点的左孩子 if head.next: head.right.next = head.next.left # 移动到当前层的下一个节点 head = head.next # 进入下一层（最左边的节点） leftmost = leftmost.left return root

核心逻辑：

“head.left.next = head.right”：连接同一个父节点下的左右孩子。
2.
“head.right.next = head.next.left”（如果
“head.next” 存在）：连接相邻父节点的左右子树。
3. 外层
“while” 逐层深入，内层
“while” 横向遍历。

方法二：递归解法（简洁直观）

递归方法利用函数调用栈隐式地完成了层序遍历，代码更简洁。

class Solution:
def connect(self, root: ‘Node’) -> ‘Node’:
if not root:
return None

# 如果有左子树（完美二叉树，有左必有右） if root.left: # 左孩子指向右孩子 root.left.next = root.right # 如果有下一个节点，右孩子指向 next 的左孩子 if root.next: root.right.next = root.next.left # 递归处理左右子树 self.connect(root.left) self.connect(root.right) return root

复杂度分析

• 时间复杂度：O(N)，每个节点只被访问一次。
• 空间复杂度：
  • 迭代法：O(1)，只使用了几个指针变量。
  • 递归法：O(log N)（即树高），由递归栈产生，符合题目进阶要求。

你可以直接将上述任一代码提交到 LeetCode 即可通过。需要我帮你分析某一种写法的执行过程，或者扩展到 LeetCode 117（普通二叉树） 的解法吗？😊