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

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

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

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

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

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

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

1.     1
2.    / \
3.   2   5
4. / \   \
5. 3   4   6

复制代码

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

1. 1
2. \
3.   2
4. / \
5. 3   4
6.      \
7.       5
8.        \
9.         6

复制代码

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

1. 1
2. \
3.   2
4.    \
5.     3
6.      \
7.       4
8.        \
9.         5
10.          \
11.           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 代码实现：

1. class Solution {
2.     public void flatten(TreeNode root) {
3.         TreeNode current = root;
4.         while (current != null) {
5.             if (current.left != null) {
6.                 // 找到左子树的最右节点
7.                 TreeNode pre = current.left;
8.                 while (pre.right != null && pre.right != current) {
9.                     pre = pre.right;
10.                 }
12.                 if (pre.right == null) {
13.                     // 将当前节点的右子树接到左子树的最右节点
14.                     pre.right = current.right;
15.                     // 将左子树移到右子树的位置
16.                     current.right = current.left;
17.                     // 将左子树置为 null
18.                     current.left = null;
19.                 }
20.             }
21.             // 移动到下一个节点
22.             current = current.right;
23.         }
24.     }
25. }

复制代码

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除