[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.

這道題給了一棵樹的先序遍歷和后序遍歷的數(shù)組，讓我們根據(jù)這兩個(gè)數(shù)組來重建出原來的二叉樹。之前也做過二叉樹的先序遍歷 [Binary Tree Preorder Traversal](http://www.cnblogs.com/grandyang/p/4146981.html) 和 后序遍歷 [Binary Tree Postorder Traversal](http://www.cnblogs.com/grandyang/p/4251757.html)，所以應(yīng)該對其遍歷的順序并不陌生。其實(shí)二叉樹最常用的三種遍歷方式，先序，中序，和后序遍歷，只要知道其中的任意兩種遍歷得到的數(shù)組，就可以重建出原始的二叉樹，而且正好都在 LeetCode 中有出現(xiàn)，其他兩道分別是 [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 的題。

我們知道，先序遍歷的順序是 根->左->右，而后序遍歷的順序是 左->右->根，既然要建立樹，那么肯定要從根結(jié)點(diǎn)開始創(chuàng)建，然后再創(chuàng)建左右子結(jié)點(diǎn)，若你做過很多樹相關(guān)的題目的話，就會知道大多數(shù)都是用遞歸才做，那么創(chuàng)建的時(shí)候也是對左右子結(jié)點(diǎn)調(diào)用遞歸來創(chuàng)建。心中有這么個(gè)概念就好，可以繼續(xù)來找這個(gè)重復(fù)的 pattern。由于先序和后序各自的特點(diǎn)，根結(jié)點(diǎn)的位置是固定的，既是先序遍歷數(shù)組的第一個(gè)，又是后序遍歷數(shù)組的最后一個(gè)，而如果給我們的是中序遍歷的數(shù)組，那么根結(jié)點(diǎn)的位置就只能從另一個(gè)先序或者后序的數(shù)組中來找了，但中序也有中序的好處，其根結(jié)點(diǎn)正好分割了左右子樹，就不在這里細(xì)講了，還是回到本題吧。知道了根結(jié)點(diǎn)的位置后，我們需要分隔左右子樹的區(qū)間，先序和后序的各個(gè)區(qū)間表示如下：

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]

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

解法一：

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 內(nèi)置的 find() 函數(shù)來查找左子樹的根結(jié)點(diǎn)在 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;
    }
};

為了進(jìn)一步優(yōu)化時(shí)間復(fù)雜度，我們可以事先用一個(gè) HashMap，來建立 post 數(shù)組中每個(gè)元素和其坐標(biāo)之間的映射，這樣在遞歸函數(shù)中，就不用進(jìn)行查找了，直接在 HashMap 中將其位置取出來用即可，用空間換時(shí)間，也不失為一個(gè)好的方法，參見代碼如下：

解法三：

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)) 提出了一種迭代的寫法，借助了棧來做，其實(shí)就用個(gè)數(shù)組就行，模擬棧的后進(jìn)先出的特性。這種設(shè)計(jì)思路很巧妙，現(xiàn)根據(jù) pre 數(shù)組進(jìn)行先序創(chuàng)建二叉樹，當(dāng)前我們的策略是，只要棧頂結(jié)點(diǎn)沒有左子結(jié)點(diǎn)，就把當(dāng)前結(jié)點(diǎn)加到棧頂元素的左子結(jié)點(diǎn)上，否則加到右子結(jié)點(diǎn)上，并把加入的結(jié)點(diǎn)壓入棧。同時(shí)我們用兩個(gè)指針i和j分別指向當(dāng)前在 pre 和 post 數(shù)組中的位置，若某個(gè)時(shí)刻，棧頂元素和 post[j] 相同了，說明當(dāng)前子樹已經(jīng)建立完成了，要將棧中當(dāng)前的子樹全部出棧，直到 while 循環(huán)的條件不滿足。這樣最終建立下來，棧中就只剩下一個(gè)根結(jié)點(diǎn)了，返回即可，參見代碼如下：

解法四：

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)

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(889.由先序和后序遍歷建立二叉樹)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)由先序和后序遍歷建立二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論