二叉樹(shù)展開(kāi)為鏈表

題目

給定一個(gè)二叉樹(shù)，原地將它展開(kāi)為一個(gè)單鏈表。

例如，給定二叉樹(shù)

    1
   / \
  2   5
 / \   \
3   4   6

將其展開(kāi)為：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

題解一

解法一 可以發(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

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

解法二

如果用先序遍歷的話(huà)，會(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;
    }
}
##解法三
看題意順序明顯是先序遍歷，二叉樹(shù)的深度遍歷本來(lái)只用遞，沒(méi)有用到歸，所以我判定把歸利用起來(lái)，肯定是能夠解題的。
一句話(huà)思路就是先序遍歷，如果走到最左邊，則把此節(jié)點(diǎn)指針?lè)祷氐接杏夜?jié)點(diǎn)的位置，把該右節(jié)點(diǎn)挪到最左邊節(jié)點(diǎn)的左邊，繼續(xù)遞歸即可。
需要注意的是，一定要注意將右節(jié)點(diǎn)接在左葉子節(jié)點(diǎn)之后記得把右節(jié)點(diǎn)清空。
還有如果將nullLeftNode左葉子節(jié)點(diǎn)指針改為全局變量會(huì)省事兒很多，不用歸，直接遞，但是考慮到原地展開(kāi)，就沒(méi)有用到外部存儲(chǔ)空間。
本解法時(shí)間復(fù)雜度O(n)，因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都遍歷了一遍；空間復(fù)雜度O(1),只有兩個(gè)臨時(shí)節(jié)點(diǎn)。

還有一種特殊的先序遍歷，提前將右孩子保存到棧中，我們利用這種遍歷方式就可以防止右孩子的丟失了。由于棧是先進(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ù)的深度遍歷本來(lái)只用遞，沒(méi)有用到歸，所以我判定把歸利用起來(lái)，肯定是能夠解題的。 一句話(huà)思路就是先序遍歷，如果走到最左邊，則把此節(jié)點(diǎn)指針?lè)祷氐接杏夜?jié)點(diǎn)的位置，把該右節(jié)點(diǎn)挪到最左邊節(jié)點(diǎn)的左邊，繼續(xù)遞歸即可。 需要注意的是，一定要注意將右節(jié)點(diǎn)接在左葉子節(jié)點(diǎn)之后記得把右節(jié)點(diǎn)清空。 還有如果將nullLeftNode左葉子節(jié)點(diǎn)指針改為全局變量會(huì)省事兒很多，不用歸，直接遞，但是考慮到原地展開(kāi)，就沒(méi)有用到外部存儲(chǔ)空間。 本解法時(shí)間復(fù)雜度O(n)，因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都遍歷了一遍；空間復(fù)雜度O(1),只有兩個(gè)臨時(shí)節(jié)點(diǎn)。

class Solution {
    public void flatten(TreeNode root) {
        if(root==null){
            return ;
        }
        //先將二叉樹(shù)轉(zhuǎn)換成左展開(kāi)鏈表
        flattenHelper(root);
        //再將左展開(kāi)轉(zhuǎn)換成右展開(kāi)鏈表
        TreeNode tempNode =root;
        while(tempNode.left!=null){
            tempNode.right = tempNode.left;
            tempNode.left = null;
            tempNode= tempNode.right;
        }
    }
    private TreeNode flattenHelper(TreeNode root){
        //如果左右節(jié)點(diǎn)都為空則返回當(dāng)前節(jié)點(diǎn)，也就是最后的左邊的節(jié)點(diǎn)；
        if(root.left==null&&root.right==null){
            return root;
        }
        //如果左為空右不為空，則把右邊的移到左邊，然后繼續(xù)遞歸左邊的；
        if(root.left==null&&root.right!=null){
            root.left=root.right;
            root.right=null;
            return flattenHelper(root.left);
        }
        //如果左不為空右為空則直接遞歸左邊的；
        if(root.left!=null&&root.right==null){
            return flattenHelper(root.left);
        }
        //如果左右都不為空則把左邊歸過(guò)來(lái)的末節(jié)點(diǎn)的左節(jié)點(diǎn)賦值為當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)，然后繼續(xù)遞歸；
            TreeNode nullLeftNode= flattenHelper(root.left);
            nullLeftNode.left = root.right;
            root.right=null;
            return flattenHelper(nullLeftNode.left);
    }
}