二叉树展开为链表

二叉树展开为链表

    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