【LeetCode 114】算法进阶：二叉树展开为链表

辖瑁地 · 2025-8-15 16:54:30

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

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

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

需要在不使用额外存储空间的情况下，直接在原二叉树上进行操作。可以使用莫里斯遍历（Morris Traversal）的思想来实现。
莫里斯遍历的核心思想：
莫里斯遍历利用了二叉树的空闲指针（左子树为空时的左指针），将其指向右子树的前驱节点，从而实现中序遍历。我们也可以利用类似的思路来展开二叉树为单链表。
算法步骤：
1.找到左子树的最右节点：
从当前节点的左子树开始，一直向右走，直到找到最右节点。
这个最右节点是左子树的最后一个节点。
2.调整指针：

将最右节点的右指针指向当前节点的右子树。
将当前节点的左子树移到右子树的位置。
将当前节点的左指针置为 null。

3.移动到下一个节点：
每次处理完一个节点后，current 指针移动到当前节点的右子树。
时间复杂度：O(n)，每个节点最多被访问两次。
空间复杂度：O(1)，不使用额外的存储空间。
下面通过一个具体的例子来模拟原地算法（莫里斯遍历）的过程：
初始状态

1
/ \
2 5
/ \ \
3 4 6

复制代码

current 指向根节点 1
第一步：处理节点 1
检查左子树：节点 1 有左子树，左子树的根是 2。
找到左子树的最右节点：从 2 开始，向右走，找到最右节点 4。
调整指针：
将 4 的右指针指向 1 的右子树（即 5）。
将 1 的左子树移到右子树的位置。
将 1 的左指针置为 null。
调整后的状态：

1
\
2
/ \
3 4
\
5
\
6

复制代码

current 移动到 2
第二步：处理节点 2
检查左子树：节点 2 有左子树，左子树的根是 3。
找到左子树的最右节点：从 3 开始，向右走，没有右节点，最右节点是 3。
调整指针：
将 3 的右指针指向 2 的右子树（即 4）。
将 2 的左子树移到右子树的位置。
将 2 的左指针置为 null。
调整后的状态：

1
\
2
\
3
\
4
\
5
\
6

复制代码

current 移动到 3
第三步：处理节点 3
检查左子树：节点 3 没有左子树。
移动到右子树：current 移动到 3 的右子树，即 4。
第四步：处理节点 4
检查左子树：节点 4 没有左子树。
移动到右子树：current 移动到 4 的右子树，即 5。
第五步：处理节点 5
检查左子树：节点 5 没有左子树。
移动到右子树：current 移动到 5 的右子树，即 6。
第六步：处理节点 6
检查左子树：节点 6 没有左子树。
移动到右子树：current 移动到 6 的右子树，但 6 没有右子树，所以 current 变为 null，结束循环。
最终状态
1 -> 2 -> 3 -> 4 -> 5 -> 6
Java 代码实现：

class Solution {
public void flatten(TreeNode root) {
TreeNode current = root;
while (current != null) {
if (current.left != null) {
// 找到左子树的最右节点
TreeNode pre = current.left;
while (pre.right != null && pre.right != current) {
pre = pre.right;
}
if (pre.right == null) {
// 将当前节点的右子树接到左子树的最右节点
pre.right = current.right;
// 将左子树移到右子树的位置
current.right = current.left;
// 将左子树置为 null
current.left = null;
}
}
// 移动到下一个节点
current = current.right;
}
}
}

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

【LeetCode 114】算法进阶：二叉树展开为链表

浏览过的版块

签约作者