C++實現LeetCode(889.由先序和後序遍歷建立二叉樹)

[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和後序遍歷建立二叉樹

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7] 

Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, …, pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

這道題給瞭一棵樹的先序遍歷和後序遍歷的數組，讓我們根據這兩個數組來重建出原來的二叉樹。之前也做過二叉樹的先序遍歷 [Binary Tree Preorder Traversal](http://www.cnblogs.com/grandyang/p/4146981.html) 和 後序遍歷 [Binary Tree Postorder Traversal](http://www.cnblogs.com/grandyang/p/4251757.html)，所以應該對其遍歷的順序並不陌生。其實二叉樹最常用的三種遍歷方式，先序，中序，和後序遍歷，隻要知道其中的任意兩種遍歷得到的數組，就可以重建出原始的二叉樹，而且正好都在 LeetCode 中有出現，其他兩道分別是 [Construct Binary Tree from Inorder and Postorder Traversal](https://www.cnblogs.com/grandyang/p/4296193.html) 和 [Construct Binary Tree from Preorder and Inorder Traversal](https://www.cnblogs.com/grandyang/p/4296500.html)。如果做過之前兩道題，那麼這道題就沒有什麼難度瞭，若沒有的話，可能還是有些 tricky 的，雖然這僅僅隻是一道 Medium 的題。

我們知道，先序遍歷的順序是 根->左->右，而後序遍歷的順序是 左->右->根，既然要建立樹，那麼肯定要從根結點開始創建，然後再創建左右子結點，若你做過很多樹相關的題目的話，就會知道大多數都是用遞歸才做，那麼創建的時候也是對左右子結點調用遞歸來創建。心中有這麼個概念就好，可以繼續來找這個重復的 pattern。由於先序和後序各自的特點，根結點的位置是固定的，既是先序遍歷數組的第一個，又是後序遍歷數組的最後一個，而如果給我們的是中序遍歷的數組，那麼根結點的位置就隻能從另一個先序或者後序的數組中來找瞭，但中序也有中序的好處，其根結點正好分割瞭左右子樹，就不在這裡細講瞭，還是回到本題吧。知道瞭根結點的位置後，我們需要分隔左右子樹的區間，先序和後序的各個區間表示如下：

preorder -> [root] [left subtree] [right subtree]
postorder -> [left subtree] [right substree] [root]

具體到題目中的例子就是：

preorder -> [1] [2,4,5] [3,6,7]
postorder -> [4,5,2] [6,7,3] [root]

先序和後序中各自的左子樹區間的長度肯定是相等的，但是其數字順序可能是不同的，但是我們仔細觀察的話，可以發現先序左子樹區間的第一個數字2，在後序左右子樹區間的最後一個位置，而且這個規律對右子樹區間同樣適用，這是為啥呢，這就要回到各自遍歷的順序瞭，先序遍歷的順序是 根->左->右，而後序遍歷的順序是 左->右->根，其實這個2就是左子樹的根結點，當然會一個在開頭，一個在末尾瞭。發現瞭這個規律，就可以根據其來定位左右子樹區間的位置范圍瞭。既然要拆分數組，那麼就有兩種方式，一種是真的拆分成小的子數組，另一種是用雙指針來指向子區間的開頭和末尾。前一種方法無疑會有大量的數組拷貝，不是很高效，所以我們這裡采用第二種方法來做。用 preL 和 preR 分別表示左子樹區間的開頭和結尾位置，postL 和 postR 表示右子樹區間的開頭和結尾位置，那麼若 preL 大於 preR 或者 postL 大於 postR 的時候，說明已經不存在子樹區間，直接返回空指針。然後要先新建當前樹的根結點，就通過 pre[preL] 取到即可，接下來要找左子樹的根結點在 post 中的位置，最簡單的方法就是遍歷 post 中的區間 [postL, postR]，找到其位置 idx，然後根據這個 idx，就可以算出左子樹區間長度為 len = (idx-postL)+1，那麼 pre 數組中左子樹區間為 [preL+1, preL+len]，右子樹區間為 [preL+1+len, preR]，同理，post 數組中左子樹區間為 [postL, idx]，右子樹區間為 [idx+1, postR-1]。知道瞭這些信息，就可以分別調用遞歸函數瞭，參見代碼如下：

解法一：

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = -1;
        for (idx = postL; idx <= postR; ++idx) {
            if (pre[preL + 1] == post[idx]) break;
        }
        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
        return node;
    }
};

我們也可以使用 STL 內置的 find() 函數來查找左子樹的根結點在 post 中的位置，其餘的地方都跟上面的解法相同，參見代碼如下：

解法二：

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = find(post.begin() + postL, post.begin() + postR + 1, pre[preL + 1]) - post.begin();
        node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
        node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
        return node;
    }
};

為瞭進一步優化時間復雜度，我們可以事先用一個 HashMap，來建立 post 數組中每個元素和其坐標之間的映射，這樣在遞歸函數中，就不用進行查找瞭，直接在 HashMap 中將其位置取出來用即可，用空間換時間，也不失為一個好的方法，參見代碼如下：

解法三：

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        unordered_map<int, int> m;
        for (int i = 0; i < post.size(); ++i) m[post[i]] = i;
        return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1, m);
    }
    TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR, unordered_map<int, int>& m) {
        if (preL > preR || postL > postR) return nullptr;
        TreeNode *node = new TreeNode(pre[preL]);
        if (preL == preR) return node;
        int idx = m[pre[preL + 1]], len = (idx - postL) + 1;
        node->left = helper(pre, preL + 1, preL + len, post, postL, idx, m);
        node->right = helper(pre, preL + 1 + len, preR, post, idx + 1, postR - 1, m);
        return node;
    }
};

論壇上 [lee215 大神](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)) 提出瞭一種迭代的寫法，借助瞭棧來做，其實就用個數組就行，模擬棧的後進先出的特性。這種設計思路很巧妙，現根據 pre 數組進行先序創建二叉樹，當前我們的策略是，隻要棧頂結點沒有左子結點，就把當前結點加到棧頂元素的左子結點上，否則加到右子結點上，並把加入的結點壓入棧。同時我們用兩個指針i和j分別指向當前在 pre 和 post 數組中的位置，若某個時刻，棧頂元素和 post[j] 相同瞭，說明當前子樹已經建立完成瞭，要將棧中當前的子樹全部出棧，直到 while 循環的條件不滿足。這樣最終建立下來，棧中就隻剩下一個根結點瞭，返回即可，參見代碼如下：

解法四：

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        vector<TreeNode*> st;
        st.push_back(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.size(); ++i) {
            TreeNode *node = new TreeNode(pre[i]);
            while (st.back()->val == post[j]) {
                st.pop_back();
                ++j;
            }
            if (!st.back()->left) st.back()->left = node;
            else st.back()->right = node;
            st.push_back(node);
        }
        return st[0];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/889

類似題目：

Binary Tree Preorder Traversal

Binary Tree Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

參考資料：

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161286/C%2B%2B-O(N)-recursive-solution

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/163540/Java-recursive-solution-beat-99.9

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)

到此這篇關於C++實現LeetCode(889.由先序和後序遍歷建立二叉樹)的文章就介紹到這瞭,更多相關C++實現由先序和後序遍歷建立二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• C++實現LeetCode(105.由先序和中序遍歷建立二叉樹)
• C++實現LeetCode(106.由中序和後序遍歷建立二叉樹)
• C++實現LeetCode(103.二叉樹的之字形層序遍歷)
• C++實現LeetCode(102.二叉樹層序遍歷)
• C++實現LeetCode(124.求二叉樹的最大路徑和)