🔗 二叉树展开为链表

题目来源：114. 二叉树展开为链表 – 力扣（LeetCode）

---

📌 题目描述

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

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

---

✅ 示例解析

示例 1：

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

解释：
先序遍历序列为 [1,2,3,4,5,6]，展开后每个节点只有右孩子，形成一条向右延伸的链。

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

---

⚠️ 提示

• 树中节点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

---

💡 解法：迭代（原地修改）—— O(n) 时间，O(1) 空间

class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left == null) {
                // 无左子树，直接向右移动
                root = root.right;
            } else {
                // 找到左子树的最右节点
                TreeNode left = root.left;
                while (left.right != null) {
                    left = left.right;
                }
                // 将原右子树接到左子树最右节点的右侧
                left.right = root.right;
                // 将左子树移到右侧
                root.right = root.left;
                root.left = null;
                // 继续处理下一个节点
                root = root.right;
            }
        }
    }
}

✅ 关键点：

• 对每个有左子树的节点，将右子树“挂”到左子树的最右端，再把左子树整体移到右边。
• 原地修改，不使用额外数据结构，空间复杂度为 O(1)。

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点最多被访问两次（一次找最右，一次主循环），总体仍是线性时间。
• 空间复杂度：O(1)
  仅使用常数个指针变量，无需递归栈或队列，真正实现原地展开。

---

🧩 解题思路

为什么能用这种“剪切-拼接”策略？

因为先序遍历顺序 = 根 → 左子树全部 → 右子树全部。
所以，对于当前节点：

1. 左子树的所有节点必须排在右子树之前；
2. 而左子树内部已是先序结构，只需将其“尾部”与右子树“头部”连接即可。

算法步骤：

1. 从根节点开始，逐个向右移动（因为展开后只有右指针）。
2. 若当前节点 没有左子树，直接进入右子树。
3. 若有左子树：
   • 找到其左子树的最右节点（即先序遍历中左子树的最后一个节点）；
   • 将当前节点的右子树接到这个最右节点的 right 上；
   • 将整个左子树移到当前节点的 right；
   • 将 left 置为 null；
4. 移动到下一个右节点，重复上述过程。

为什么找“左子树的最右节点”？

• 因为在先序遍历中，左子树的最后一个被访问的节点，就是其最右路径的末端。
• 把原右子树接在这里，就能保证先序顺序不被破坏。