二叉树扁平化为双向链表是指将一棵二叉树的节点按照中序遍历的顺序重新排列，让每个节点的左指针指向前一个节点，右指针指向后一个节点，最终形成一条双向链表，同时不再保留原有的树形结构层级关系。
核心实现思路
要实现这个转换，核心是要按照中序遍历的顺序遍历二叉树的所有节点，在遍历过程中维护前一个访问的节点，将当前节点的左指针指向前一个节点，前一个节点的右指针指向当前节点，遍历完成后就得到了双向链表。
递归实现方案
递归实现是最直观的方式，我们可以定义一个递归函数，在函数中处理当前节点的左右子树，同时记录遍历过程中的前一个节点。
首先定义二叉树的节点结构，代码如下：
// 二叉树节点定义
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
递归实现的核心代码如下：
public class BinaryTreeFlatten {
// 记录前一个遍历的节点
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
// 先递归处理右子树
flatten(root.right);
// 再递归处理左子树
flatten(root.left);
// 当前节点的左指针指向前一个节点
root.left = prev;
// 前一个节点的右指针指向当前节点
if (prev != null) {
prev.right = root;
}
// 更新前一个节点为当前节点
prev = root;
}
}
上述代码采用逆中序遍历的方式，先处理右子树再处理左子树，这样遍历的顺序就是中序遍历的逆序，最终得到的双向链表是从大到小排列的。如果需要从小到大排列，只需要调整递归顺序，先处理左子树再处理右子树即可。
迭代实现方案
递归实现虽然简洁，但是在树深度很大的时候可能会出现栈溢出的问题，这时候可以使用迭代的方式实现，通过栈来模拟递归过程。
迭代实现的核心代码如下：
import java.util.Stack;
public class BinaryTreeFlattenIterative {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode prev = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
// 先将右节点入栈，保证左节点先出栈，实现中序遍历
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
// 处理当前节点和前一个节点的指针关系
curr.left = prev;
if (prev != null) {
prev.right = curr;
}
prev = curr;
// 断开当前节点的原有左右指针，避免保留树形结构
curr.left = prev;
curr.right = null;
}
}
}
两种方案对比
我们可以从时间复杂度、空间复杂度和适用场景三个方面对比两种实现方案：
| 实现方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归实现 | O(n)，n为节点数，每个节点仅访问一次 | O(h)，h为树的高度，递归栈深度 | 树深度较小，代码简洁性要求高的场景 |
| 迭代实现 | O(n)，每个节点仅访问一次 | O(n)，栈的最大存储节点数 | 树深度较大，需要避免栈溢出的场景 |
注意事项
- 转换完成后需要确认所有节点的原有树形指针已经被正确修改，避免出现环或者残留的树形结构引用。
- 如果二叉树本身存在重复值，需要提前确认遍历顺序是否符合业务需求，避免链表顺序不符合预期。
- 操作过程中如果修改了原有二叉树的结构，需要确认业务是否允许修改原树，若不允许则需要先拷贝原树再操作。
实际应用场景
这种转换操作在很多场景下有实际应用，比如需要将树形存储的菜单数据转换为线性结构方便前端渲染，或者需要对树节点按照顺序进行批量操作的时候，转换为双向链表后可以方便地进行正向和反向遍历，提升操作效率。
如果需要在转换后的链表上快速查找某个节点，还可以结合哈希表记录每个节点的值和对应的节点引用，将查找时间复杂度降低到O(1)。