详解二叉树展开为链表：从递归到 O(1) 空间优化

详解二叉树展开为链表：从递归到 O(1) 空间优化

在二叉树的算法面试题中，'Flatten Binary Tree to Linked List' (将二叉树展开为链表) 是一道非常经典的题目（LeetCode 114）。它不仅考察我们对树遍历的理解，更考察我们在改变树结构时对指针的掌控能力。

本文将基于三种不同的思路——递归先序遍历、迭代栈模拟以及空间复杂度 O(1) 的原地变换进行思考。

题目核心目标

给定一个二叉树的根节点 root，我们需要将其展开为一个单链表：

1. 展开后的链表顺序应与二叉树的先序遍历（根 → 左 → 右）顺序一致。
2. 单链表使用 TreeNode 的 right 指针构建，所有节点的 left 指针必须设为 null。
3. 原地修改，不能创建新的节点。

---

方法一：递归先序遍历 (直观解法)

最符合直觉的方法是直接按照先序遍历的逻辑进行递归。但是，这道题的难点在于：我们在遍历的同时正在破坏原本的树结构。

如果我们直接修改当前节点的 right 指针，原本的右子树就会丢失。为了解决这个问题，我们需要在修改指针前对右子节点进行备份。

代码实现

class Solution {
    // 全局指针，始终指向当前已处理链表的最后一个节点
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        preorder(root);
    }

    private void preorder(TreeNode node) {
        if (node == null) return;

        // 1. 链接操作：如果有前驱节点，将其右指针指向当前节点，左指针置空
        if (prev != null) {
            prev.left = null;
            prev.right = node;
        }

        // 2. 指针推进：当前节点成为新的链表尾部
        prev = node;

        // 3. 关键备份：暂存右子节点
        // 原因：下一步递归左子树时，prev (即当前 node) 的 right 指针会被修改指向左子节点
        // 若不备份，原右子树的引用将丢失
        TreeNode right = node.right;

        preorder(node.left);
        preorder(right);
    }
}

该方法逻辑清晰，但需要 O(N) 的递归栈空间。后续可探讨如何进一步优化至 O(1) 空间复杂度。