二叉树展开为链表
二叉树展开为链表
1
/ \
2 5
/ \ \
3 4 6
可以发现展开的顺序其实就是二叉树的先序遍历。算法Morris 算法有些神似，我们需要两步完成这道题。
思路：
将原来的右子树接到左子树的最右边节点
将左子树插入到右子树的地方
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
可以看图理解下这个过程 :
处理过程.png
时间复杂度：O(n)，其中 n 是二叉树的节点数。展开为单链表的过程中，需要对每个节点访问一次，在寻找前驱节点的过程中，每个节点最多被额外访问一次。
空间复杂度：O(1)
代码的话也很好写，首先我们需要找出左子树最右边的节点以便把右子树接过来
class Solution {
public void flatten(TreeNode root) {
while(root != null) {
//1. 左子树为空，直接考虑下一个节点
if(root.left==null) {
root = root.right;
}else {//2 左子树不为空
//2.1 寻找左子树的最右节点
TreeNode pre = root.left;
while(pre.right != null) {
pre = pre.right;
}
//2.2 将原来的右子树接到左子树的最右节点
pre.right = root.right;
//2.3 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;//清空左子树
//2.4 处理下一个节点
root = root.right;
}
}
}
}
提交结果.png
解法二
题目中，要求说是 in-place，之前一直以为这个意思就是要求空间复杂度是 O(1)
O(1)。 in-place 的意思是直接在原来的节点上改变指向，空间复杂度并没有要求。所以这道题也可以用递归解一下
利用递归的话，可能比解法一难理解一些。题目其实就是将二叉树通过右指针，组成一个链表。
1 -> 2 -> 3 -> 4 -> 5 -> 6
我们知道题目给定的遍历顺序其实就是先序遍历的顺序，所以我们能不能利用先序遍历的代码，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
先序遍历的顺序是 1 2 3 4 5 6。
遍历到 2，把 1 的右指针指向 2。1 -> 2 3 4 5 6。
遍历到 3，把 2 的右指针指向 3。1 -> 2 -> 3 4 5 6。
... ...
一直进行下去似乎就解决了这个问题。但现实是残酷的，原因就是我们把 1 的右指针指向 2，那么 1 的原本的右孩子就丢失了，也就是 5 就找不到了。
解决方法的话，我们可以逆过来进行。
我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点。
遍历到 5，把 5 的右指针指向 6。6 <- 5 4 3 2 1。
遍历到 4，把 4 的右指针指向 5。6 <- 5 <- 4 3 2 1。
... ...
这样就不会有丢失孩子的问题了，因为更新当前的右指针的时候，当前节点的右孩子已经访问过了。
而 6 5 4 3 2 1 的遍历顺序其实变形的后序遍历，遍历顺序是右子树->左子树->根节点。
先回想一下后序遍历的代码
public void PrintBinaryTreeBacRecur(TreeNode<T> root){
if (root == null)
return;
PrintBinaryTreeBacRecur(root.right);
PrintBinaryTreeBacRecur(root.left);
System.out.print(root.data);
}
这里的话，我们不再是打印根节点，而是利用一个全局变量 pre，更新当前根节点的右指针为 pre，左指针为 null。
private TreeNode pre = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
}
相应的左孩子也要置为 null，同样的也不用担心左孩子丢失，因为是后序遍历，左孩子已经遍历过了。
时间复杂度：O(n)，其中 n 是二叉树的节点数。展开为单链表的过程中，需要对每个节点访问一次
空间复杂度：O(1)
提交结果.png
