二叉树展开为链表

来源Leetcode第114二叉树展开为链表

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

---

栈的先序遍历

由题目可知这是一道先序遍历的题目，于是考虑了用栈，通过栈提前保存二叉树的右左子树，然后通过出栈解决。
但是与普通的二叉树先序遍历不一样，需要对出栈节点的左子树赋值为null，并且保存当前遍历节点。
代码如下:

public void flatten(TreeNode root) {
    if(root == null)
        return ;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp = null;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode tmp = stack.pop();
        if(temp != null){
            temp.right = tmp;
            temp.left = null;
        }
        if (tmp.right != null)
            stack.push(tmp.right);
        if (tmp.left != null)
            stack.push(tmp.left);
        temp = tmp;
    }
}

Morris遍历

来自题解

可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。

1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

可以看图理解下这个过程。

   1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  
  ......

于是相应的，代码如下：

public void flatten(TreeNode root) {
    while(root != null){
        if(root.left == null){
            root = root.right;  //左子树为空可以直接进行下一层的遍历
        }
        else{
            TreeNode tmp = root.left;
            while (tmp.right != null)
                tmp = tmp.right;
            tmp.right = root.right;  //根节点右子树成为左子树最右节点
            root.right = root.left;  //根节点的右子树成为左子树
            root.left = null;  //根节点左子树赋值为空
            root = root.right;  //进行下一个节点的遍历
        }
    }
}

递归

我们可以逆过来进行。

我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点。

遍历到 5，把 5 的右指针指向 6。6 <- 5 4 3 2 1。

遍历到 4，把 4 的右指针指向 5。6 <- 5 <- 4 3 2 1。

… …

    1
   / \
  2   5
 / \   \
3   4   6

这样就不会有丢失孩子的问题了，因为更新当前的右指针的时候，当前节点的右孩子已经访问过了。

而 6 5 4 3 2 1 的遍历顺序其实变形的后序遍历，遍历顺序是右子树->左子树->根节点。

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;
}