二叉树原地展平为双向链表是指将二叉树的节点按照中序遍历的顺序重新排列，每个节点的左指针指向双向链表的前驱节点，右指针指向后继节点，整个过程不创建新的节点，仅调整原有节点的指针指向。
问题核心分析
要实现原地转换，首先需要明确两个关键点：一是节点的排列顺序遵循二叉树的中序遍历结果，二是每个节点的左右指针需要分别指向双向链表的前一个和后一个节点。如果额外创建新的链表节点，就不符合原地操作的要求，因此必须在原有二叉树节点的基础上调整指针。
中序遍历的顺序是左子树、根节点、右子树，这个顺序刚好符合双向链表的节点排列逻辑。我们可以在中序遍历的过程中，记录上一个访问的节点，将当前节点的左指针指向上一个节点，上一个节点的右指针指向当前节点，这样就能逐步构建出双向链表。
递归实现方案
递归是实现这个转换的常用方式，核心思路是定义一个全局或者引用传递的变量，用来保存中序遍历过程中的前一个节点，遍历到当前节点时调整两个节点的指针指向。
节点结构定义
首先定义二叉树的节点结构，该节点同时作为双向链表的节点使用：
// 二叉树节点定义，同时也是双向链表节点
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
递归转换逻辑
递归函数的逻辑分为三步：先递归处理左子树，再处理当前节点，最后递归处理右子树。处理当前节点时，调整当前节点和前驱节点的指针：
public class BinaryTreeToList {
// 保存中序遍历的前一个节点
private TreeNode prev = null;
public TreeNode flattenToDoublyList(TreeNode root) {
if (root == null) {
return null;
}
// 递归处理左子树
flattenToDoublyList(root.left);
// 处理当前节点
if (prev != null) {
// 前驱节点的右指针指向当前节点
prev.right = root;
// 当前节点的左指针指向前驱节点
root.left = prev;
}
// 更新前驱节点为当前节点
prev = root;
// 递归处理右子树
flattenToDoublyList(root.right);
// 找到链表的头节点，即最左的节点
TreeNode head = root;
while (head.left != null) {
head = head.left;
}
return head;
}
}
代码逻辑说明
上述代码中，prev变量用来记录中序遍历过程中上一个访问的节点。当处理当前节点root时，如果prev不为空，说明已经存在前驱节点，就将prev.right指向当前节点，root.left指向prev，完成两个节点的双向连接。之后更新prev为当前节点，继续遍历右子树。最后通过向左遍历找到双向链表的头节点返回。
迭代实现方案
除了递归，也可以使用迭代的方式结合栈实现中序遍历，完成指针调整，避免递归带来的栈溢出风险，适合处理节点数量较多的二叉树。
public TreeNode flattenToDoublyListIterative(TreeNode root) {
if (root == null) {
return null;
}
TreeNode prev = null;
TreeNode head = null;
java.util.Stack<TreeNode> stack = new java.util.Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 遍历到最左节点
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 弹出栈顶节点处理
curr = stack.pop();
// 处理当前节点和前驱节点的指针
if (prev == null) {
// 第一个节点是链表头
head = curr;
} else {
prev.right = curr;
curr.left = prev;
}
prev = curr;
// 处理右子树
curr = curr.right;
}
return head;
}
边界情况处理
实现过程中需要注意几个边界情况：
- 如果二叉树为空，直接返回null即可，不需要做任何处理。
- 如果二叉树只有一个节点，那么该节点既是双向链表的头也是尾，左右指针都为null。
- 如果二叉树只有左子树或者只有右子树，转换后的双向链表依然符合中序遍历的顺序，指针调整逻辑依然适用。
复杂度分析
无论是递归还是迭代实现，时间复杂度都是O(n)，其中n是二叉树的节点数量，因为每个节点只会被访问一次。空间复杂度方面，递归实现的空间复杂度是O(h)，h是二叉树的高度，最坏情况下是O(n)（当二叉树退化为链表时）；迭代实现的空间复杂度是O(h)，同样取决于栈的最大深度。
验证示例
我们可以用一个简单的二叉树验证转换结果：
public static void main(String[] args) {
// 构建二叉树： 1
// /
// 2 3
// /
// 4 5
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
BinaryTreeToList solution = new BinaryTreeToList();
TreeNode head = solution.flattenToDoublyList(root);
// 正向遍历双向链表
TreeNode curr = head;
System.out.println("正向遍历结果：");
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.right;
}
// 输出应为：4 2 5 1 3
}
上述示例中，二叉树的中序遍历结果是4、2、5、1、3，转换后的双向链表正向遍历也会得到这个结果，说明转换逻辑是正确的。