題目描述（中等難度）

把一個(gè)二叉樹(shù)展開(kāi)成一個(gè)鏈表，展開(kāi)順序如圖所示。

解法一

可以發(fā)現(xiàn)展開(kāi)的順序其實(shí)就是二叉樹(shù)的先序遍歷。算法和 94 題 中序遍歷的 Morris 算法有些神似，我們需要兩步完成這道題。

1. 將左子樹(shù)插入到右子樹(shù)的地方
2. 將原來(lái)的右子樹(shù)接到左子樹(shù)的最右邊節(jié)點(diǎn)
3. 考慮新的右子樹(shù)的根節(jié)點(diǎn)，一直重復(fù)上邊的過(guò)程，直到新的右子樹(shù)為 null

可以看圖理解下這個(gè)過(guò)程。

    1
   / \
  2   5
 / \   \
3   4   6

//將 1 的左子樹(shù)插入到右子樹(shù)的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//將原來(lái)的右子樹(shù)接到左子樹(shù)的最右邊節(jié)點(diǎn)
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //將 2 的左子樹(shù)插入到右子樹(shù)的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //將原來(lái)的右子樹(shù)接到左子樹(shù)的最右邊節(jié)點(diǎn)
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  
  ......

代碼的話也很好寫(xiě)，首先我們需要找出左子樹(shù)最右邊的節(jié)點(diǎn)以便把右子樹(shù)接過(guò)來(lái)。

public void flatten(TreeNode root) {
    while (root != null) { 
        //左子樹(shù)為 null，直接考慮下一個(gè)節(jié)點(diǎn)
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子樹(shù)最右邊的節(jié)點(diǎn)
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //將原來(lái)的右子樹(shù)接到左子樹(shù)的最右邊節(jié)點(diǎn)
            pre.right = root.right;
            // 將左子樹(shù)插入到右子樹(shù)的地方
            root.right = root.left;
            root.left = null;
            // 考慮下一個(gè)節(jié)點(diǎn)
            root = root.right;
        }
    }
}

解法二

題目中，要求說(shuō)是in-place，之前一直以為這個(gè)意思就是要求空間復(fù)雜度是O(1)。偶然看見(jiàn)評(píng)論區(qū) StefanPochmann 大神的解釋。

也就是說(shuō)in-place 的意思可能更多說(shuō)的是直接在原來(lái)的節(jié)點(diǎn)上改變指向，空間復(fù)雜度并沒(méi)有要求。所以這道題也可以用遞歸解一下，參考 這里 。

    1
   / \
  2   5
 / \   \
3   4   6

利用遞歸的話，可能比解法一難理解一些。

題目其實(shí)就是將二叉樹(shù)通過(guò)右指針，組成一個(gè)鏈表。

1 -> 2 -> 3 -> 4 -> 5 -> 6

我們知道題目給定的遍歷順序其實(shí)就是先序遍歷的順序，所以我們能不能利用先序遍歷的代碼，每遍歷一個(gè)節(jié)點(diǎn)，就將上一個(gè)節(jié)點(diǎn)的右指針更新為當(dāng)前節(jié)點(diǎn)。

先序遍歷的順序是1 2 3 4 5 6。

遍歷到2，把1的右指針指向2。1 -> 2 3 4 5 6。

遍歷到3，把2的右指針指向3。1 -> 2 -> 3 4 5 6。

... ...

一直進(jìn)行下去似乎就解決了這個(gè)問(wèn)題。但現(xiàn)實(shí)是殘酷的，原因就是我們把1的右指針指向2，那么1的原本的右孩子就丟失了，也就是5 就找不到了。

解決方法的話，我們可以逆過(guò)來(lái)進(jìn)行。

我們依次遍歷6 5 4 3 2 1，然后每遍歷一個(gè)節(jié)點(diǎn)就將當(dāng)前節(jié)點(diǎn)的右指針更新為上一個(gè)節(jié)點(diǎn)。

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

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

... ...

    1
   / \
  2   5
 / \   \
3   4   6

這樣就不會(huì)有丟失孩子的問(wèn)題了，因?yàn)楦庐?dāng)前的右指針的時(shí)候，當(dāng)前節(jié)點(diǎn)的右孩子已經(jīng)訪問(wèn)過(guò)了。

而6 5 4 3 2 1的遍歷順序其實(shí)變形的后序遍歷，遍歷順序是右子樹(shù)->左子樹(shù)->根節(jié)點(diǎn)。

先回想一下變形的后序遍歷的代碼

public void PrintBinaryTreeBacRecur(TreeNode<T> root){
    if (root == null)
        return;
    
    PrintBinaryTreeBacRecur(root.right);
    PrintBinaryTreeBacRecur(root.left); 
    System.out.print(root.data);
    
} 

這里的話，我們不再是打印根節(jié)點(diǎn)，而是利用一個(gè)全局變量pre，更新當(dāng)前根節(jié)點(diǎn)的右指針為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;
}

相應(yīng)的左孩子也要置為null，同樣的也不用擔(dān)心左孩子丟失，因?yàn)槭呛笮虮闅v，左孩子已經(jīng)遍歷過(guò)了。和 112 題 一樣，都巧妙的利用了后序遍歷。

既然后序遍歷這么有用，利用 112 題 介紹的后序遍歷的迭代方法，把這道題也改一下吧。

public void flatten(TreeNode root) { 
    Stack<TreeNode> toVisit = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;

    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根節(jié)點(diǎn)
            cur = cur.right; // 遞歸添加右節(jié)點(diǎn)
        }
        cur = toVisit.peek(); // 已經(jīng)訪問(wèn)到最右的節(jié)點(diǎn)了
        // 在不存在左節(jié)點(diǎn)或者右節(jié)點(diǎn)已經(jīng)訪問(wèn)過(guò)的情況下，訪問(wèn)根節(jié)點(diǎn)
        if (cur.left == null || cur.left == pre) {
            toVisit.pop(); 
            /**************修改的地方***************/
            cur.right = pre;
            cur.left = null;
            /*************************************/
            pre = cur;
            cur = null;
        } else {
            cur = cur.left; // 左節(jié)點(diǎn)還沒(méi)有訪問(wèn)過(guò)就先訪問(wèn)左節(jié)點(diǎn)
        }
    } 
}

解法三

解法二中提到如果用先序遍歷的話，會(huì)丟失掉右孩子，除了用后序遍歷，還有沒(méi)有其他的方法避免這個(gè)問(wèn)題。在Discuss又發(fā)現(xiàn)了一種解法，參考 這里。

為了更好的控制算法，所以我們用先序遍歷迭代的形式，正常的先序遍歷代碼如下，

public static void preOrderStack(TreeNode root) {
    if (root == null) { 
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    while (root != null || !s.isEmpty()) {
        while (root != null) {
            System.out.println(root.val);
            s.push(root);
            root = root.left;
        }
        root = s.pop();
        root = root.right;
    }
}

還有一種特殊的先序遍歷，提前將右孩子保存到棧中，我們利用這種遍歷方式就可以防止右孩子的丟失了。由于棧是先進(jìn)后出，所以我們先將右節(jié)點(diǎn)入棧。

public static void preOrderStack(TreeNode root) {
    if (root == null){
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(root);
    while (!s.isEmpty()) {
        TreeNode temp = s.pop();
        System.out.println(temp.val);
        if (temp.right != null){
            s.push(temp.right);
        }
        if (temp.left != null){
            s.push(temp.left);
        }
    }
}

之前我們的思路如下：

題目其實(shí)就是將二叉樹(shù)通過(guò)右指針，組成一個(gè)鏈表。

1 -> 2 -> 3 -> 4 -> 5 -> 6

我們知道題目給定的遍歷順序其實(shí)就是先序遍歷的順序，所以我們可以利用先序遍歷的代碼，每遍歷一個(gè)節(jié)點(diǎn)，就將上一個(gè)節(jié)點(diǎn)的右指針更新為當(dāng)前節(jié)點(diǎn)。

先序遍歷的順序是1 2 3 4 5 6。

遍歷到2，把1的右指針指向2。1 -> 2 3 4 5 6。

遍歷到3，把2的右指針指向3。1 -> 2 -> 3 4 5 6。

... ...

因?yàn)槲覀冇脳１４媪擞液⒆?，所以不需要?dān)心右孩子丟失了。用一個(gè)pre變量保存上次遍歷的節(jié)點(diǎn)。修改的代碼如下：

public void flatten(TreeNode root) { 
    if (root == null){
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(root);
    TreeNode pre = null;
    while (!s.isEmpty()) {
        TreeNode temp = s.pop(); 
        /***********修改的地方*************/
        if(pre!=null){
            pre.right = temp;
            pre.left = null;
        }
        /********************************/
        if (temp.right != null){
            s.push(temp.right);
        }
        if (temp.left != null){
            s.push(temp.left);
        } 
        /***********修改的地方*************/
        pre = temp;
        /********************************/
    }
}

總

解法一和解法三可以看作自頂向下的解決問(wèn)題，解法二可以看作自底向上。以前覺(jué)得后序遍歷比較麻煩，沒(méi)想到竟然連續(xù)遇到了后序遍歷的應(yīng)用。先序遍歷的兩種方式自己也是第一次意識(shí)到，之前都是用的第一種正常的方式。

更多詳細(xì)通俗題解詳見(jiàn) leetcode.wang 。