详解二叉树展开为链表：从递归到 O(1) 空间的极致优化
详解二叉树展开为链表：从递归到 O(1)O(1)O(1) 空间的极致优化
在二叉树的算法面试题中，“Flatten Binary Tree to Linked List” (将二叉树展开为链表) 是一道非常经典的题目（LeetCode 114）。它不仅考察我们对树遍历的理解，更考察我们在改变树结构时对指针的掌控能力。
本文将基于三种不同的思路——递归先序遍历、迭代栈模拟以及空间复杂度 O(1)O(1)O(1) 的原地变换进行思考。
题目核心目标
给定一个二叉树的根节点 root，我们需要将其展开为一个单链表：
- 展开后的链表顺序应与二叉树的先序遍历（根 →\rightarrow→ 左 →\rightarrow→ 右）顺序一致。
- 单链表使用
TreeNode的right指针构建，所有节点的left指针必须设为null。 - 原地修改，不能创建新的节点。
方法一：递归先序遍历 (直观解法)
最符合直觉的方法是直接按照先序遍历的逻辑进行递归。但是，这道题的难点在于：我们在遍历的同时正在破坏原本的树结构。
如果我们直接修改当前节点的 right 指针，原本的右子树就会丢失。为了解决这个问题，我们需要在修改指针前对右子节点进行备份。
代码实现
classSolution{ // 全局指针，始终指向当前已处理链表的最后一个节点privateTreeNode prev =null;publicvoidflatten(TreeNode root){ if(root ==null)return;preorder(root);}privatevoidpreorder(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
