本教程详细探讨了如何将二叉树原地（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. 注意事项与总结
- 原地修改： 扁