首页 > 营销学院 > 技术知识

深度解析二叉树原地展平为双向链表结构

本文深入探讨了如何将二叉树原地展平为类似双向链表的结构。通过递归方法，文章详细解释了在展平过程中，如何正确地处理左右子树的连接，特别是对关键指针（如`leftmostofright`和`rightmostofleft`）初始值设定的理解，以及避免创建循环引用的重要性。最终，提供并解析了一个高度优化的递归实现，展示了如何高效地重构树节点指针以实现所需的扁平化结构。

理解二叉树展平问题

将二叉树展平为双向链表结构是一个常见的算法问题，其核心要求是将树的节点按照特定的遍历顺序（通常是中序遍历的逻辑顺序，即从左到右）连接起来，形成一个类似双向链表的结构。在这个结构中，原始的 left 指针将充当链表的 prev 指针，而 right 指针则充当链表的 next 指针。展平操作必须是“原地”（in-place）完成的，这意味着我们不能创建新的节点，只能修改现有节点的 left 和 right 指针。最终函数需要返回展平后链表的最左侧（即第一个）节点。

每个 BinaryTree 节点包含一个 value、一个 left 子节点和一个 right 子节点，子节点可以是 BinaryTree 实例或 None。

初始递归策略与常见困惑

为了实现原地展平，一个直观的思路是使用递归辅助函数。这个辅助函数通常会返回当前子树展平后的最左节点和最右节点，以便父节点能够正确地将它们连接起来。

考虑以下初始的递归辅助函数结构：

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
    if node.left is None and node.right is None: # 优化后此特殊处理可省略
        return node, node

    leftmostofleft = node # 初始假设：当前节点是左侧最左节点
    rightmostofright = node # 初始假设：当前节点是右侧最右节点
    leftmostofright = None  # 初始假设：右子树的最左节点为空
    rightmostofleft = None  # 初始假设：左子树的最右节点为空

    # 处理左子树
    if node.left:
        leftmostofleft, rightmostofleft = helper(node.left)
    # 处理右子树
    if node.right:
        leftmostofright, rightmostofright = helper(node.right)

    # 连接当前节点与左右子树展平后的结构
    # 将当前节点的右指针指向右子树展平后的最左节点
    node.right = leftmostofright
    if leftmostofright:
        leftmostofright.left = node # 建立双向链接

    # 将当前节点的左指针指向左子树展平后的最右节点
    node.left = rightmostofleft
    if rightmostofleft:
        rightmostofleft.right = node # 建立双向链接

    return leftmostofleft, rightmostofright

在这个实现中，一个常见的困惑点在于 leftmostofright 和 rightmostofleft 的初始赋值。为什么它们应该默认为 None，而不是 node？

如果将它们初始化为 node，例如：

leftmostofleft = node
rightmostofright = node
leftmostofright = node # 假设这里也初始化为 node
rightmostofleft = node # 假设这里也初始化为 node

当 node 没有右子节点时，if node.right: 条件将不满足，leftmostofright 就会保持其初始值 node。接着，执行 node.right = leftmostofright，这会变成 node.right = node。这将导致 node 形成一个指向自身的循环引用，破坏了链表的结构，也无法正确地连接后续节点。

正确理解：leftmostofright 代表的是当前节点 node 的右子树展平后的最左节点。如果 node 没有右子树，那么它就没有“右子树展平后的最左节点”，因此这个概念应该用 None 来表示，而不是 node 自身。将 node.right 设置为 None 是正确的行为，表示其链表中的下一个节点不存在。同理，rightmostofleft 也应如此处理。

leftmostofleft 和 rightmostofright 初始为 node 是合理的，因为在没有左右子树的情况下，当前节点 node 就是其自身展平后的最左和最右节点。

HIX Translate

由 ChatGPT 提供支持的智能AI翻译器

114 查看详情 HIX Translate

优化后的递归实现

上述 helper 函数可以进一步简化和优化，去除不必要的 if 条件和中间变量，使其更加简洁高效。关键在于理解 node.left 和 node.right 指针在展平过程中被“重用”的语义。

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
    # helper函数返回的是展平后链表的 (最左节点, 最右节点)
    # 对于整个树的展平，我们只需要返回最左节点
    leftmost_node, _ = _flatten_helper(root)
    return leftmost_node

def _flatten_helper(node):
    # 如果节点为空，则返回 (None, None)，表示空链表
    if node is None:
        return None, None

    # 初始化当前节点的展平链表的左右边界为自身
    leftmost_in_subtree = node
    rightmost_in_subtree = node

    # 递归处理左子树
    if node.left:
        # 展平左子树，得到其最左节点 (L_left) 和最右节点 (R_left)
        L_left, R_left = _flatten_helper(node.left)

        # 更新当前子树的最左节点为左子树的最左节点
        leftmost_in_subtree = L_left

        # 将当前节点的左指针指向左子树展平后的最右节点 (R_left)
        # 这就是链表中当前节点的前一个节点
        node.left = R_left

        # 建立 R_left 到当前节点的右向连接
        R_left.right = node

    # 递归处理右子树
    if node.right:
        # 展平右子树，得到其最左节点 (L_right) 和最右节点 (R_right)
        L_right, R_right = _flatten_helper(node.right)

        # 将当前节点的右指针指向右子树展平后的最左节点 (L_right)
        # 这就是链表中当前节点的后一个节点
        node.right = L_right

        # 建立 L_right 到当前节点的左向连接
        L_right.left = node

        # 更新当前子树的最右节点为右子树的最右节点
        rightmost_in_subtree = R_right

    # 返回当前节点展平后子树的最左和最右节点
    return leftmost_in_subtree, rightmost_in_subtree

代码解析：

_flatten_helper(node) 函数返回 (leftmost_in_subtree, rightmost_in_subtree)：
- leftmost_in_subtree 是以 node 为根的子树展平后，整个链表结构的最左侧节点。
- rightmost_in_subtree 是以 node 为根的子树展平后，整个链表结构的最右侧节点。
基本情况 if node is None:：
- 当遇到空节点时，返回 (None, None)，表示没有节点。
初始化 leftmost_in_subtree = node, rightmost_in_subtree = node：
- 在处理 node 自身时，如果它没有左右子树，那么它就是自身展平后的最左和最右节点。这些变量会在递归调用后根据实际情况更新。
处理左子树 if node.left:：
- L_left, R_left = _flatten_helper(node.left)：递归地展平左子树。L_left 是左子树展平后的第一个节点，R_left 是最后一个节点。
- leftmost_in_subtree = L_left：因为 L_left 在 node 之前，所以它是整个当前子树展平后的最左节点。
- node.left = R_left：关键步骤。将当前节点 node 的 left 指针指向其左子树展平后的最右节点 R_left。这建立了 node 与其在链表中的前一个节点 R_left 的连接。
- R_left.right = node：关键步骤。建立从 R_left 到 node 的反向连接，完成双向链接。
处理右子树 if node.right:：
- L_right, R_right = _flatten_helper(node.right)：递归地展平右子树。L_right 是右子树展平后的第一个节点，R_right 是最后一个节点。
- node.right = L_right：关键步骤。将当前节点 node 的 right 指针指向其右子树展平后的最左节点 L_right。这建立了 node 与其在链表中的后一个节点 L_right 的连接。
- L_right.left = node：关键步骤。建立从 L_right 到 node 的反向连接，完成双向链接。
- rightmost_in_subtree = R_right：因为 R_right 在 node 之后，并且是右子树的最后一个节点，所以它是整个当前子树展平后的最右节点。
返回 return leftmost_in_subtree, rightmost_in_subtree：
- 将当前子树展平后的最左和最右节点返回给上一级递归调用。

注意事项与总结

原地操作（In-place）：这个解决方案严格遵循了原地操作的要求，没有创建任何新的 BinaryTree 节点，只是修改了现有节点的 left 和 right 指针。
递归的深度优先遍历：该方法本质上是深度优先遍历的一种变体，通过递归将子问题解决后，再将结果合并到父节点。
指针的重用与语义转换：理解 node.left 和 node.right 指针从“树的子节点”转换为“链表的上一个/下一个节点”是理解此算法的关键。
处理空子树：当节点没有左子树或右子树时，相应的 if 条件不会满足，因此不会进行额外的连接操作，这自然地处理了边界情况，避免了不必要的 None 检查和循环引用。
时间复杂度：每个节点只访问常数次（一次递归调用），所以时间复杂度为 O(N)，其中 N 是树中的节点数。
空间复杂度：递归调用的栈空间取决于树的高度。在最坏情况下（链表型树），空间复杂度为 O(N)；在最好情况下（平衡树），空间复杂度为 O(logN)。

通过上述优化后的实现，我们可以高效且清晰地将任意二叉树原地展平为一个双向链表结构，同时避免了常见的指针混淆和循环引用问题。

以上就是深度解析二叉树原地展平为双向链表结构的详细内容，更多请关注其它相关文章！

# 正确地 # 漯河全网推广营销招聘 # 广东企业seo案例 # 长春网站建设怎么选专业 # 荣成网站建设制作 # 枝江推广网站 # 装饰公司如何做网站推广 # 底线素材网站建设需要 # 霍州网站关键词优化排名 # 常熟公司网站建设方法 # 锡山seo网站优化 # 在这个 # node # 的是 # 如何用 # 第一个 # 二叉树 # 遍历 # 链表 # 递归 # 子树 # 为什么 # 栈

相关栏目：【 Google疑问12 】【 Facebook疑问10 】【优化推广96088 】【技术知识133117 】【 IDC资讯59369 】【网络运营7196 】【 IT资讯61894 】

2025-12-08

SQL多表关联如何理解_核心原理解析助你掌握关键方法【教程】 SQL多表连接如何理解_JOIN关联关系详细步骤解析【指导】 SQL多表连接结果异常怎么办_JOIN条件排查方法解析【指导】 SQL索引下推是什么_ICP机制性能提升原理【教程】 SQL跨表统计怎么写_重要技巧总结提升查询效率【技巧】 SQL注入如何防护_完整逻辑拆解助力系统化掌握【技巧】 SQL上传文件信息建模方法_SQL存储文件元数据方案 SQL多语种存储方案设计_SQL字符集选择策略 SQL字符串处理如何编写_重要技巧总结提升查询效率【教学】 SQL去重查询怎么实现_优化思路讲解帮助高效处理数据【技巧】 SQL统计复购用户怎么做_多次行为分析SQL思路【教程】 SQL字符串处理如何编写_优化思路讲解帮助高效处理数据【教程】 SQL动态字段解析技巧_SQL解析JSON多层字段 SQL线上慢SQL如何治理_规范与工具实践总结【技巧】 SQL表结构如何演进_兼容老数据设计思路【教程】 SQL排序规则如何设置_ORDERBY排序原理与性能说明【指导】 SQL去重查询怎么实现_真实案例解析强化复杂查询思维【教学】 SQL按字段范围分批处理_SQL避免长时间锁表 SQL统计不同字段组合数量_多列聚合查询技巧【技巧】 SQL多字段去重怎么处理_GROUPBY去重思路说明【教学】

了解您产品搜索量及市场趋势，制定营销计划

同行竞争及网站分析保障您的广告效果

点击免费数据支持

提交您的需求，1小时内享受我们的专业解答。

运城市盐湖区信雨科技有限公司

运城市盐湖区信雨科技有限公司是一家深耕海外推广领域十年的专业服务商，作为谷歌推广与Facebook广告全球合作伙伴，聚焦外贸企业出海痛点，以数字化营销为核心，提供一站式海外营销解决方案。公司凭借十年行业沉淀与平台官方资源加持，打破传统外贸获客壁垒，助力企业高效开拓全球市场，成为中小企业出海的可靠合作伙伴。