二叉树原地扁平化为双向链表结构：原理与优化实践-Python教程-PHP中文网

二叉树原地扁平化为双向链表结构：原理与优化实践

本教程详细探讨了如何将二叉树原地（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，例如：

标贝悦读AI配音

在线文字转语音软件-专业的配音网站

查看详情

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]

登录后复制