轉(zhuǎn)自網(wǎng)友題解

題目

給定一個二叉樹，原地將它展開為鏈表。

例如，給定二叉樹
    1
   / \
  2   5
 / \   \
3   4   6
將其展開為：
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解法一

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

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

可以看圖理解下這個過程。

    1
   / \
  2   5
 / \   \
3   4   6

//將 1 的左子樹插入到右子樹的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//將原來的右子樹接到左子樹的最右邊節(jié)點
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //將 2 的左子樹插入到右子樹的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //將原來的右子樹接到左子樹的最右邊節(jié)點
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         

代碼的話也很好寫，首先我們需要找出左子樹最右邊的節(jié)點以便把右子樹接過來。

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

解法二

題目中，要求說是in-place，之前一直以為這個意思就是要求空間復(fù)雜度是。偶然看見評論區(qū) StefanPochmann大神的解釋。

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

    1
   / \
  2   5
 / \   \
3   4   6

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

題目其實就是將二叉樹通過右指針，組成一個鏈表。

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

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

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

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

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

... ...

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

解決方法的話，我們可以逆過來進行。

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

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

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

... ...

    1
   / \
  2   5
 / \   \
3   4   6

這樣就不會有丟失孩子的問題了，因為更新當(dāng)前的右指針的時候，當(dāng)前節(jié)點的右孩子已經(jīng)訪問過了。

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

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

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

這里的話，我們不再是打印根節(jié)點，而是利用一個全局變量pre，更新當(dāng)前根節(jié)點的右指針為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)心左孩子丟失，因為是后序遍歷，左孩子已經(jīng)遍歷過了。和 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é)點
            cur = cur.right; // 遞歸添加右節(jié)點
        }
        cur = toVisit.peek(); // 已經(jīng)訪問到最右的節(jié)點了
        // 在不存在左節(jié)點或者右節(jié)點已經(jīng)訪問過的情況下，訪問根節(jié)點
        if (cur.left == null || cur.left == pre) {
            toVisit.pop(); 
            /**************修改的地方***************/
            cur.right = pre;
            cur.left = null;
            /*************************************/
            pre = cur;
            cur = null;
        } else {
            cur = cur.left; // 左節(jié)點還沒有訪問過就先訪問左節(jié)點
        }
    } 
}

解法三

解法二中提到如果用先序遍歷的話，會丟失掉右孩子，除了用后序遍歷，還有沒有其他的方法避免這個問題。在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;
    }
}

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

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

之前我們的思路如下：

題目其實就是將二叉樹通過右指針，組成一個鏈表。

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

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

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

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

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

... ...

因為我們用棧保存了右孩子，所以不需要擔(dān)心右孩子丟失了。用一個pre變量保存上次遍歷的節(jié)點。修改的代碼如下：

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

總結(jié)

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