二叉树转双向链表详细解析

本文深入探讨了如何将二叉树原地展平为类似双向链表的结构。通过递归方法，文章详细解释了在展平过程中，如何正确地处理左右子树的连接，特别是对关键指针（如`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 就是其自身展平后的最左和最右节点。

优化后的递归实现

上述 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

代码解析：

1. _flatten_helper(node) 函数返回 (leftmost_in_subtree, rightmost_in_subtree)：

   • leftmost_in_subtree 是以 node 为根的子树展平后，整个链表结构的最左侧节点。
   • rightmost_in_subtree 是以 node 为根的子树展平后，整个链表结构的最右侧节点。

2. 基本情况 if node is None:：

   • 当遇到空节点时，返回 (None, None)，表示没有节点。

3. 初始化 leftmost_in_subtree = node, rightmost_in_subtree = node：

   • 在处理 node 自身时，如果它没有左右子树，那么它就是自身展平后的最左和最右节点。这些变量会在递归调用后根据实际情况更新。

4. 处理左子树 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 的反向连接，完成双向链接。

5. 处理右子树 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 之后，并且是右子树的最后一个节点，所以它是整个当前子树展平后的最右节点。

6. 返回 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)。

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