LeetCode 第 114 题：二叉树展开为链表（Flatten Binary Tree to Linked List）

题目描述

给定一棵二叉树的根节点 root，请你使用原地（in-place） 算法将这棵二叉树展开为一个单链表：

1. 展开后的单链表应该与二叉树的先序遍历（根 -> 左子树 -> 右子树）顺序相同。
2. 展开后的链表节点，其右子指针指向链表中的下一个节点，而左子指针始终为 null。

示例：
给定二叉树：

    1
   / \
  2   5
 / \   \
3   4   6

展开后变为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解题思路（循序渐进）

第一步：理解题意与关键点

1. 顺序要求：展开后的链表节点顺序，必须与对这棵二叉树进行先序遍历得到的节点顺序完全一致。
2. 结构要求：每个节点的 left 指针必须设为 null，right 指针指向链表中的下一个节点。
3. 原地算法：题目要求使用原地算法，这意味着我们不能先遍历一遍将节点值存入一个列表，再重新构建链表。我们需要直接在原树上通过修改指针来完成操作。空间复杂度最好为 O(1)（不考虑递归调用栈的话）。

第二步：初步思考——先序遍历的局限性

我们最容易想到的方法是：先对二叉树进行一次先序遍历，将遍历到的节点按顺序保存在一个列表（比如 list）中。

然后，我们再遍历这个 list，对于第 i 个节点：

• 将它的 left 指针设为 null。
• 将它的 right 指针指向第 i+1 个节点。

这种方法直观且正确，但它的空间复杂度是 O(n)，因为我们需要一个额外的列表来存储所有 n 个节点。这不符合原地算法的要求。

第三步：寻找原地修改的方法——核心思路“找前驱”

我们需要一种在遍历过程中就能直接修改指针的方法。核心观察点是：对于一个节点 root，在先序遍历中，root 的下一个节点是它的左子树的根节点（如果左子树存在的话）。而左子树遍历完后，下一个要遍历的是 root 的右子树。

那么，我们如何将 root 的右子树“接”到左子树遍历完的后面呢？

1. 当前节点操作：假设当前我们位于节点 root。

2. 处理左子树：如果 root 有左子树，我们需要将整个左子树“转移”到右子树的位置。

   • 首先，我们找到 root 的左子树中进行先序遍历的最后一个节点。这个节点我们称之为 predecessor（前驱节点）。因为先序遍历是“根 -> 左 -> 右”，所以左子树的最后一个节点，就是左子树中最右下角的那个节点。
   • 然后，我们将 root 的整个右子树，“挂到”这个 predecessor 节点的右指针（right）上。因为 predecessor 是先序遍历中左子树的最后一个节点，它的后面本来就应该接上 root 的右子树。
   • 最后，我们将 root 的左子树“提升”为右子树：即把 root 的 right 指针指向原来的左子树，并将 left 指针设为 null。

3. 移动节点：完成上述操作后，root 的右子节点变成了它原来的左子节点。我们让 root 指向这个新的右子节点（即原来的左子节点），继续重复上述过程。

4. 处理右子树：如果 root 没有左子树，那么说明当前节点的“根部”已经符合链表结构，我们只需要简单地移动到它的右子节点，继续处理即可。

这个过程确保了我们在遍历树的同时，也完成了指针的修改。

第四步：详细步骤分解（配合示例）

我们以示例二叉树 [1, 2, 5, 3, 4, null, 6] 来一步步分解：

初始状态：

    1 (root)
   / \
  2   5
 / \   \
3   4   6

步骤 1：处理节点 1

• 当前节点 root 是 1。
• 节点 1 有左子树（节点 2）。
• 找到节点 1 的左子树（以 2 为根）的先序遍历的最后一个节点。这个子树先序遍历是 2 -> 3 -> 4，所以最后一个节点是 4。predecessor 是节点 4。
• 将节点 1 的右子树（以 5 为根）挂到 predecessor (节点 4) 的右边：4.right = 5。
• 将节点 1 的左子树“提升”为右子树：1.right = 1.left (即节点 2)，然后 1.left = null。

此时结构变为：

1
 \
  2
 / \
3   4
     \
      5
       \
        6

(注意：节点 5 和 6 现在挂在了节点 4 的下面)

步骤 2：处理节点 2（原节点 1 的右子节点，即原左子节点）

• 当前节点 root 是 2。
• 节点 2 有左子树（节点 3）。
• 找到节点 2 的左子树（以 3 为根）的先序遍历的最后一个节点。这个子树只有一个节点 3，所以 predecessor 就是节点 3。
• 将节点 2 的右子树（以 4 为根，现在挂着 5 和 6）挂到 predecessor (节点 3) 的右边：3.right = 4。
• 将节点 2 的左子树“提升”为右子树：2.right = 2.left (即节点 3)，然后 2.left = null。

此时结构变为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

(链表形状已经初步形成)

步骤 3：处理节点 3

• 当前节点 root 是 3。
• 节点 3 没有左子树。
• 不需要进行“找前驱”和“挂右子树”的操作。
• 我们直接移动到节点 3 的右子节点，即节点 4。

步骤 4：处理节点 4

• 当前节点 root 是 4。
• 节点 4 没有左子树。
• 直接移动到节点 4 的右子节点，即节点 5。

步骤 5：处理节点 5

• 当前节点 root 是 5。
• 节点 5 有左子树吗？没有（注意，原来的左子树是 null）。
• 但是节点 5 有右子树（节点 6）。
• 对于节点 5，它没有左子树，所以我们不需要做“找前驱”和“提升”的操作，直接移动到它的右子节点 6。

步骤 6：处理节点 6

• 节点 6 是叶子节点，没有左右子树。处理结束。

最终，二叉树被展开成了符合要求的单链表。

第五步：代码实现（迭代法）

这种思路通常使用迭代法来实现，因为它可以方便地在修改指针的同时移动当前节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        curr = root
        while curr:
            # 如果当前节点有左子树，才需要进行操作
            if curr.left:
                # 1. 找到当前节点左子树的前驱节点（左子树最右边的节点）
                predecessor = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
                
                # 2. 将当前节点的右子树接到前驱节点的右边
                predecessor.right = curr.right
                
                # 3. 将当前节点的左子树“提升”到右边，并置空左指针
                curr.right = curr.left
                curr.left = None
            
            # 移动到当前节点的右子节点（即原来的左子节点，或者下一个节点）
            curr = curr.right

第六步：复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。我们每个节点最多被访问两次：一次是作为 curr 被遍历，另一次是作为某个节点的左子树的一部分被寻找前驱时遍历。但总体仍然是 O(n) 级别。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间（curr 和 predecessor 指针），满足了原地算法的要求。

总结

解决这个问题的关键在于发现“将右子树挂到左子树的前驱节点上”这一操作。通过迭代地执行“找前驱 -> 挂右子树 -> 提升左子树”这三步，我们可以在先序遍历的顺序下，逐步将二叉树拉平成单链表，并且只使用常数的额外空间。