本教程详细探讨了如何将二叉树原地（in-place）扁平化为一种类似双向链表的结构。文章首先阐述了扁平化的核心目标和节点连接顺序，接着分析了递归实现中常见的指针初始化误区，特别是避免创建不必要的循环引用。最后，提供了一种经过优化的递归解决方案，通过直接更新父节点指针并返回子树的边界节点，实现了更简洁高效的扁平化操作，并附带了完整的代码示例和注意事项。
1. 二叉树扁平化概述
二叉树扁平化是将一个二叉树结构转换为一种线性结构，使其节点按照特定的遍历顺序（通常是左-根-右，即中序遍历的逻辑顺序）排列，形成一个类似双向链表的结构。这里的“类似双向链表”意味着树节点的 left 和 right 指针将分别充当链表的 prev 和 next 指针。扁平化操作通常要求是“原地”（in-place）进行，即直接修改原树节点的指针，不创建新的节点，并且最终返回扁平化后链表的“最左侧”节点（即原树中序遍历的第一个节点）。
扁平化目标：
- 将二叉树转换为一个线性结构。
- 节点顺序遵循原树的左-根-右（中序）逻辑顺序。
- left 指针指向前一个节点，right 指针指向后一个节点。
- 操作必须是原地修改。
2. 递归扁平化策略
实现二叉树原地扁平化的一种有效方法是采用递归策略。核心思想是为每个节点设计一个辅助函数，该函数负责扁平化当前节点的左右子树，然后将这些扁平化的子树与当前节点连接起来，最终返回当前子树的扁平化结果的“最左侧”和“最右侧”节点。
假设我们的辅助函数 helper(node) 能够返回一个元组 (leftmost, rightmost)，分别代表以 node 为根的子树扁平化后的链表的头节点和尾节点。
2.1 初始实现分析与常见误区
考虑以下一种递归辅助函数的初始实现思路：
class BinaryTree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def flattenBinaryTree(root):
if not root:
return None
leftmost, _ = helper(root)
return leftmost
def helper(node):
if node is None:
return None, None
# 初始默认值
leftmost_of_current_subtree = node
rightmost_of_current_subtree = node
# 用于存储左右子树扁平化后的边界节点
leftmost_of_right_child_subtree = None
rightmost_of_left_child_subtree = None
# 处理左子树
if node.left:
leftmost_of_current_subtree, rightmost_of_left_child_subtree = helper(node.left)
# 处理右子树
if node.right:
leftmost_of_right_child_subtree, rightmost_of_current_subtree = helper(node.right)
# 连接当前节点与左右子树
# 将当前节点的右指针指向其右子树扁平化后的最左节点
node.right = leftmost_of_right_child_subtree
if leftmost_of_right_child_subtree:
leftmost_of_right_child_subtree.left = node # 右子树的最左节点指回当前节点
# 将当前节点的左指针指向其左子树扁平化后的最右节点
node.left = rightmost_of_left_child_subtree
if rightmost_of_left_child_subtree:
rightmost_of_left_child_subtree.right = node # 左子树的最右节点指回当前节点
return leftmost_of_current_subtree, rightmost_of_current_subtree误区分析：为什么 leftmost_of_right_child_subtree 和 rightmost_of_left_child_subtree 不能默认初始化为 node？
在上述代码中，leftmost_of_right_child_subtree 和 rightmost_of_left_child_subtree 被初始化为 None。如果尝试将它们也初始化为 node，例如：
leftmost_of_current_subtree = node rightmost_of_current_subtree = node leftmost_of_right_child_subtree = node # 错误尝试 rightmost_of_left_child_subtree = node # 错误尝试
这将导致问题。考虑一个只有左子树而没有右子树的节点（例如，node.right 为 None）。在这种情况下，if node.right: 条件不会被满足，leftmost_of_right_child_subtree 将保持其默认值 node。
随后，执行到连接逻辑时：
node.right = leftmost_of_right_child_subtree # 此时，node.right 将被赋值为 node
这将导致 node.right 指向 node 自身，形成一个循环引用。这不仅破坏了链表结构，也与我们期望的 node.right 为 None 的情况（当没有右子树时）相悖。
因此，当一个节点没有某个子树时，其对应的连接指针（例如 node.right 或 node.left）应该指向 None。将 leftmost_of_right_child_subtree 和 rightmost_of_left_child_subtree 初始化为 None，并在子树存在时才更新它们，可以有效避免这种不必要的自循环或错误连接。
2.2 优化后的递归实现
上述实现虽然能够工作，但存在一些冗余和可以简化的地方。例如，叶子节点不需要特殊处理，并且可以通过更直接的方式进行指针赋值。以下是经过优化的 helper 函数：
def helper_optimized(node):
# 如果节点为空，则没有扁平化结果，返回 None, None
if node is None:
return None, None
# 初始化当前子树的扁平化后的最左和最右节点为当前节点本身
# 这是在没有子节点情况下的默认值
leftmost_in_subtree = node
rightmost_in_subtree = node
# 递归处理左子树
if node.left:
# 扁平化左子树，获取其最左和最右节点
# leftmost_of_left_child: 左子树扁平化后的最左节点
# rightmost_of_left_child: 左子树扁平化后的最右节点
leftmost_of_left_child, rightmost_of_left_child = helper_optimized(node.left)
# 更新当前子树的最左节点为左子树的最左节点
leftmost_in_subtree = leftmost_of_left_child
# 将左子树扁平化后的最右节点连接到当前节点
rightmost_of_left_child.right = node
node.left = rightmost_of_left_child # 当前节点的left指针指向左子树的rightmost
# 递归处理右子树
if node.right:
# 扁平化右子树，获取其最左和最右节点
# leftmost_of_right_child: 右子树扁平化后的最左节点
# rightmost_of_right_child: 右子树扁平化后的最右节点
leftmost_of_right_child, rightmost_of_right_child = helper_optimized(node.right)
# 更新当前子树的最右节点为右子树的最右节点
rightmost_in_subtree = rightmost_of_right_child
# 将当前节点连接到右子树扁平化后的最左节点
leftmost_of_right_child.left = node
node.right = leftmost_of_right_child # 当前节点的right指针指向右子树的leftmost
# 返回当前子树扁平化后的最左和最右节点
return leftmost_in_subtree, rightmost_in_subtree优化版 helper_optimized 的核心逻辑：
- 基准情况： 如果 node 为 None，直接返回 (None, None)。
- 初始化边界： leftmost_in_subtree 和 rightmost_in_subtree 默认设置为当前 node。这意味着如果 node 是一个叶子节点，它就是其自身扁平化后的最左和最右节点。
-
处理左子树：
- 如果 node.left 存在，递归调用 helper_optimized(node.left) 获取左子树扁平化后的最左节点 leftmost_of_left_child 和最右节点 rightmost_of_left_child。
- 更新当前子树的整体最左节点：leftmost_in_subtree = leftmost_of_left_child。
- 建立双向链接：rightmost_of_left_child.right = node (左子树的最右节点指向当前节点)，node.left = rightmost_of_left_child (当前节点指向左子树的最右节点)。
-
处理右子树：
- 如果 node.right 存在，递归调用 helper_optimized(node.right) 获取右子树扁平化后的最左节点 leftmost_of_right_child 和最右节点 rightmost_of_right_child。
- 更新当前子树的整体最右节点：rightmost_in_subtree = rightmost_of_right_child。
- 建立双向链接：leftmost_of_right_child.left = node (右子树的最左节点指回当前节点)，node.right = leftmost_of_right_child (当前节点指向右子树的最左节点)。
- 返回结果： 返回 (leftmost_in_subtree, rightmost_in_subtree)。
这种优化后的方法避免了中间变量的过多使用，通过直接更新 node.left 和 node.right 指针，并巧妙地利用递归返回的边界节点来构建双向链表。
3. 完整的代码示例
class BinaryTree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# 为了测试方便，添加一个插入方法
def insert(self, values, i=0):
if i >= len(values):
return self
queue = [self]
while len(queue) > 0:
current = queue.pop(0)
if current.left is None:
current.left = BinaryTree(values[i])
break
queue.append(current.left)
if current.right is None:
current.right = BinaryTree(values[i])
break
queue.append(current.right)
self.insert(values, i + 1)
return self
# 为了测试方便，添加一个从左到右再到左的遍历方法
def leftToRightToLeft(self):
nodes = []
current = self
# 从最左节点开始向右遍历
while current.right is not None:
nodes.append(current.value)
current = current.right
nodes.append(current.value) # 添加最右节点
# 从最右节点开始向左遍历
while current is not None:
nodes.append(current.value)
current = current.left
return nodes
def flattenBinaryTree(root):
"""
将二叉树原地扁平化为双向链表结构，并返回链表的头节点。
"""
if not root:
return None
leftmost_node, _ = helper_optimized(root)
return leftmost_node
def helper_optimized(node):
"""
递归辅助函数，扁平化以当前节点为根的子树，并返回扁平化后链表的头尾节点。
返回: (leftmost_in_subtree, rightmost_in_subtree)
"""
if node is None:
return None, None
leftmost_in_subtree = node
rightmost_in_subtree = node
# 处理左子树
if node.left:
# 递归扁平化左子树
leftmost_of_left_child, rightmost_of_left_child = helper_optimized(node.left)
# 更新当前子树的最左节点
leftmost_in_subtree = leftmost_of_left_child
# 将左子树扁平化后的最右节点连接到当前节点
rightmost_of_left_child.right = node
node.left = rightmost_of_left_child
# 处理右子树
if node.right:
# 递归扁平化右子树
leftmost_of_right_child, rightmost_of_right_child = helper_optimized(node.right)
# 更新当前子树的最右节点
rightmost_in_subtree = rightmost_of_right_child
# 将当前节点连接到右子树扁平化后的最左节点
leftmost_of_right_child.left = node
node.right = leftmost_of_right_child
return leftmost_in_subtree, rightmost_in_subtree
# --- 测试用例 ---
if __name__ == "__main__":
# 构建测试树:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# / \
# 7 8
root = BinaryTree(1).insert([2, 3, 4, 5, 6])
root.left.right.left = BinaryTree(7)
root.left.right.right = BinaryTree(8)
print("原始树结构 (中序遍历):")
# 模拟中序遍历来验证节点顺序
def inorder_traversal(node, result):
if node:
inorder_traversal(node.left, result)
result.append(node.value)
inorder_traversal(node.right, result)
original_inorder = []
inorder_traversal(root, original_inorder)
print(original_inorder) # 预期: [4, 2, 7, 5, 8, 1, 6, 3]
print("\n扁平化二叉树...")
leftMostNode = flattenBinaryTree(root)
print("扁平化后链表 (从左到右再到左遍历):")
# 预期结果：[4, 2, 7, 5, 8, 1, 6, 3, 3, 6, 1, 8, 5, 7, 2, 4]
# 第一次遍历 [4, 2, 7, 5, 8, 1, 6, 3]
# 第二次遍历 [3, 6, 1, 8, 5, 7, 2, 4]
print(leftMostNode.leftToRightToLeft())
# 验证扁平化后的顺序
current = leftMostNode
flattened_values = []
while current:
flattened_values.append(current.value)
current = current.right
print("扁平化后从左到右顺序:", flattened_values) # 预期: [4, 2, 7, 5, 8, 1, 6, 3]
# 验证双向链接
if flattened_values:
print("验证双向链接 (从右到左):")
current = flattened_values[-1] # 从最右节点开始
reversed_flattened_values = []
while current:
reversed_flattened_values.append(current.value)
current = current.left
print("扁平化后从右到左顺序:", reversed_flattened_values) # 预期: [3, 6, 1, 8, 5, 7, 2, 4]4. 注意事项与总结
- 原地修改： 扁
