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

本教程详细探讨了如何将二叉树原地（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 的核心逻辑：

1. 基准情况： 如果 node 为 None，直接返回 (None, None)。
2. 初始化边界： leftmost_in_subtree 和 rightmost_in_subtree 默认设置为当前 node。这意味着如果 node 是一个叶子节点，它就是其自身扁平化后的最左和最右节点。
3. 处理左子树：
   • 如果 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 (当前节点指向左子树的最右节点)。
4. 处理右子树：
   • 如果 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 (当前节点指向右子树的最左节点)。
5. 返回结果： 返回 (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. 注意事项与总结

• 原地修改： 扁

# node  # app  # ai  # 优化实践  # 排列  # 为什么  # if  # 递归  # 循环  # 指针  # 子树  # 扁平化  # 遍历  # 链表  # 二叉树  # 连接到  # 默认值  # 再到  # 转换为 

相关文章： 网站制作公司排行榜,抖音怎样做个人官方网站  ,如何利用word制作宣传手册？  道歉网站制作流程,世纪佳缘致歉小吴事件，相亲网站身份信息伪造该如何稽查？  Avalonia如何实现跨窗口通信 Avalonia窗口间数据传递  济南企业网站制作公司,济南社保单位网上缴费步骤？  如何配置IIS站点权限与局域网访问？  制作网站的网址是什么,请问后缀为.com和.com.cn还有.cn的这三种网站是分别是什么类型的网站？  北京制作网站的公司,北京铁路集团官方网站？  如何选择高效可靠的多用户建站源码资源？  建站VPS选购需注意哪些关键参数？  如何自定义建站之星网站的导航菜单样式？  做企业网站制作流程,企业网站制作基本流程有哪些？  如何在Golang中指定模块版本_使用go.mod控制版本号  免费公司网站制作软件,如何申请免费主页空间做自己的网站？  如何快速上传建站程序避免常见错误？  建站之星价格显示格式升级，你的预算足够吗？  西安市网站制作公司,哪个相亲网站比较好?西安比较好的相亲网站？  如何打造高效商业网站？建站目的决定转化率  武汉外贸网站制作公司,现在武汉外贸前景怎么样啊？  如何将凡科建站内容保存为本地文件？  如何用PHP快速搭建高效网站？分步指南  建站之星代理商如何保障技术支持与售后服务？  如何用IIS7快速搭建并优化网站站点？  深圳网站制作公司好吗,在深圳找工作哪个网站最好啊？  如何在局域网内绑定自建网站域名？  怎么将XML数据可视化 D3.js加载XML  建站主机无法访问？如何排查域名与服务器问题  建站之星安装后如何自定义网站颜色与字体？  制作网站的基本流程,设计网站的软件是什么？  简单实现Android文件上传  PHP 500报错的快速解决方法  东莞市网站制作公司有哪些,东莞找工作用什么网站好？  代购小票制作网站有哪些,购物小票的简要说明？  c++怎么编写动态链接库dll_c++ __declspec(dllexport)导出与调用【方法】  如何在云指建站中生成FTP站点？  长春网站建设制作公司,长春的网络公司怎么样主要是能做网站的？  大连网站制作费用,大连新青年网站，五年四班里的视频怎样下载啊？  早安海报制作网站推荐大全,企业早安海报怎么每天更换？  中山网站推广排名,中山信息港登录入口？  外汇网站制作流程,如何在工商银行网站上做外汇买卖？  如何在云主机快速搭建网站站点？  建站之星官网登录失败？如何快速解决？  网站制作大概要多少钱一个,做一个平台网站大概多少钱？  如何通过VPS建站实现广告与增值服务盈利？  网站微信制作软件,如何制作微信链接？  建站主机空间推荐 高性价比配置与快速部署方案解析  建站之星免费模板：自助建站系统与智能响应式一键生成  建站之星会员如何解锁更多建站功能？  公司门户网站制作流程,华为官网怎么做？  ,巨量百应是干嘛的？