17370845950

本教程详细阐述如何将二叉树原地展平为类似双向链表的结构，使其节点按中序遍历顺序排列，并返回展平后的最左节点。文章将深入分析递归展平的核心逻辑，特别解释在处理子树缺失时，如何正确设置指针以避免循环引用，并提供优化后的python实现及详细解释，帮助读者掌握这一常见的树结构转换技巧。

1. 二叉树展平问题概述

二叉树展平（Flatten Binary Tree）是一个常见的树结构转换问题，其目标是将一个给定的二叉树原地（in-place）转换为一个类似于双向链表的结构。具体要求如下：

• 结构转换：转换后的结构应类似于双向链表，其中节点的 left 指针扮演链表的 prev 指针，right 指针扮演链表的 next 指针。
• 节点顺序：展平后的节点应遵循原始二叉树的左-根-右（中序）遍历顺序。
• 原地操作：转换必须在原数据结构上进行，不允许创建新的节点或复制整个树。
• 返回值：函数应返回展平后链表的“最左节点”（即原始树中序遍历的第一个节点）。

例如，如果输入是一个二叉搜索树（BST），展平后的链表将是排序的。

为了实现这一目标，我们需要一个 BinaryTree 类定义，通常包含 value、left 和 right 属性：

class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

2. 核心思路：递归展平与指针连接

解决二叉树展平问题的常用方法是递归。我们可以定义一个辅助函数 helper(node)，它的职责是展平以 node 为根的子树，并返回展平后子树的最左节点和最右节点。通过这种方式，父节点可以利用子树展平后的边界节点来正确连接自身。

假设 helper(node) 返回 (leftmost, rightmost)，其中 leftmost 是展平后子树的最左节点，rightmost 是展平后子树的最右节点。

对于当前节点 node：

1. 递归展平其左子树，得到 (leftmost_of_left_subtree, rightmost_of_left_subtree)。
2. 递归展平其右子树，得到 (leftmost_of_right_subtree, rightmost_of_right_subtree)。
3. 将 node 与其展平后的左子树和右子树连接起来。
   • node 的 left 指针应该指向 rightmost_of_left_subtree（作为其前一个节点）。
   • node 的 right 指针应该指向 leftmost_of_right_subtree（作为其后一个节点）。
   • 相应地，rightmost_of_left_subtree 的 right