114.二叉树展开为链表

题目描述

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

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题解

解法一

这道题可以看作是, 从根节点开始遍历, 将左子树挂在右子树的位置, 然后将右子树挂在原左子树的最右节点的右子树位置.

    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) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left!=null){
            TreeNode temp = cur.right;
            cur.right = cur.left;
            cur.left = null;
            TreeNode cur2 = cur;
            while (cur2.right!=null){
                cur2 = cur2.right;
            }
            cur2.right = temp;
        }
        cur = cur.right;
    }
}

后序遍历+递归

一开始我是想用先序遍历做的, 因为展开后的顺序就是先序遍历的结果. 每遍历到一个节点就让上一个节点的右指针指向当前节点. 做法是创建一个全局变量pre它表示的是上一个节点. 遍历到一个节点, 就让它称为pre的右儿子, 但是有个问题就是, 当把节点2放在pre的右边后, 节点5就要消失了, 再也找不回来. 退栈时右边本来应该是节点5, 但是不存在了.

所以只能用后序遍历的方法, 从底向上地连接链表. 连接顺序改变一下即可, 遍历到当前节点时, 令其右指针指向上一个节点. 遍历的顺序改为先遍历右子树

class Solution {
    TreeNode tail = null;

    public void flatten(TreeNode root) {
        if (root != null) {
            flatten(root.right);
            flatten(root.left);
            
            root.right = tail;
            root.left = null;
            tail = root;
        }
    }
}