114. 二叉树展开为链表

---

题目

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

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

示例： 示例 1:

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

示例 2:

输入: root = []
输出: []

示例 3:

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

---

解题思路

核心方法

递归法（后序遍历）：通过后序遍历先处理右子树，再处理左子树，最后处理根节点，将左子树接到根节点的右指针，再将原右子树接到左子树的最右节点，从而实现前序遍历的链表展开。

算法步骤

1. 终止条件：当前节点为 null 时，直接返回。
2. 递归处理右子树：先递归展开右子树。
3. 递归处理左子树：再递归展开左子树。
4. 调整指针：
   • 将当前节点的右指针指向 pre（上一个处理的节点）。
   • 将当前节点的左指针置为 null。
   • 更新 pre 为当前节点。
5. 完成展开：递归结束后，整棵树已展开为单链表。

---

代码实现

递归法（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    TreeNode pre = null;
    
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }
}

迭代法（Java）

import java.util.*;

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if (pre != null) {
                pre.right = curr;
                pre.left = null;
            }
            // 先压右子树，再压左子树，保证前序遍历顺序
            if (curr.right != null) stack.push(curr.right);
            if (curr.left != null) stack.push(curr.left);
            pre = curr;
        }
    }
}

---

复杂度分析

递归法

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

迭代法

• 时间复杂度：O(n)，每个节点会被入栈和出栈一次。
• 空间复杂度：O(h)，栈的大小取决于树的高度。

---

总结

1. 递归法通过后序遍历和全局变量 pre 记录上一个节点，实现了原地展开，空间效率较高。
2. 迭代法使用栈模拟前序遍历，通过调整指针实现链表展开，避免了递归栈溢出的风险。
3. 两种方法均实现了原地展开，时间效率一致，空间效率取决于树的高度。

---