二叉树展开为链表

题目描述
给定一个二叉树的根节点 root，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而 left 子指针始终为 null。
• 展开后的单链表应该与二叉树的 先序遍历 顺序相同。

示例

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解题过程

步骤 1：理解展开要求

• 展开后的链表节点顺序必须等于二叉树的 先序遍历（根 → 左子树 → 右子树）顺序。
• 需要 原地修改，即直接修改节点的指针，而不是创建新节点。

关键难点

• 如果直接先序遍历并存储节点顺序，再重新连接，需要 O(n) 额外空间。
• 题目要求 O(1) 额外空间（递归栈除外）的解法。

步骤 2：寻找规律
考虑先序遍历中相邻节点的关系：

1. 当前节点 curr 的左子树的最右下节点（左子树的先序遍历最后一个节点）的右指针，应该指向 curr 的右子树。
2. 然后将 curr 的右指针指向左子树，左指针置空。

具体操作（对于当前节点 curr）：

1. 若 curr.left 为 null，直接处理右子树。
2. 若 curr.left 不为 null：
   • 找到 curr.left 子树中的最右下节点 pre（即左子树先序遍历的最后一个节点）。
   • 将 pre.right 指向 curr.right。
   • 将 curr.right 指向 curr.left，curr.left 置为 null。
3. 移动到下一个节点（即新的 curr.right，因为左子树已经移到右边）。

步骤 3：示例推导
以 root = [1,2,5,3,4,null,6] 为例：

1. 当前节点 1：左子树为 2，左子树的最右下节点是 4（因为 2 → 3 → 4）。
   • 4.right 指向 1 的右子树 5。
   • 1.right 指向 2，1.left 置 null。
   • 此时链表：1 → 2 → 3 → 4 → 5。
2. 当前节点 2：左子树为 3，最右下节点是 3（无右子）。
   • 3.right 指向 2 的右子树 4。
   • 2.right 指向 3，2.left 置 null。
   • 链表：1 → 2 → 3 → 4 → 5。
3. 当前节点 3：无左子树，直接处理右子树 4。
4. 当前节点 4：无左子树，处理右子树 5。
5. 当前节点 5：左子树为空，但右子树为 6，直接连接。
   最终得到：1 → 2 → 3 → 4 → 5 → 6。

步骤 4：代码实现

def flatten(root):
    curr = root
    while curr:
        if curr.left:
            # 找到左子树的最右下节点
            pre = curr.left
            while pre.right:
                pre = pre.right
            # 将 pre 的右指针指向 curr 的右子树
            pre.right = curr.right
            # 将 curr 的右指针指向左子树，左指针置空
            curr.right = curr.left
            curr.left = None
        # 移动到下一个节点
        curr = curr.right

• 时间复杂度：O(n)，每个节点被访问常数次。
• 空间复杂度：O(1)（除递归栈外）。

步骤 5：总结

• 核心思想：利用先序遍历的规律，将左子树插入到当前节点与右子树之间。
• 关键操作：寻找左子树的最右下节点，用于连接当前节点的右子树。
• 该方法避免了显式存储先序遍历序列，实现了原地展开。