C++如何實現(xiàn)由先序和后序建立二叉樹

今天小編給大家分享一下C++如何實現(xiàn)由先序和后序建立二叉樹的相關(guān)知識點，內(nèi)容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

由先序和后序遍歷建立二叉樹

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ù)這兩個數(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ù)組，就可以重建出原始的二叉樹，而且正好都在 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é)點開始創(chuàng)建，然后再創(chuàng)建左右子結(jié)點，若你做過很多樹相關(guān)的題目的話，就會知道大多數(shù)都是用遞歸才做，那么創(chuàng)建的時候也是對左右子結(jié)點調(diào)用遞歸來創(chuàng)建。心中有這么個概念就好，可以繼續(xù)來找這個重復(fù)的 pattern。由于先序和后序各自的特點，根結(jié)點的位置是固定的，既是先序遍歷數(shù)組的第一個，又是后序遍歷數(shù)組的最后一個，而如果給我們的是中序遍歷的數(shù)組，那么根結(jié)點的位置就只能從另一個先序或者后序的數(shù)組中來找了，但中序也有中序的好處，其根結(jié)點正好分割了左右子樹，就不在這里細講了，還是回到本題吧。知道了根結(jié)點的位置后，我們需要分隔左右子樹的區(qū)間，先序和后序的各個區(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ù)字順序可能是不同的，但是我們仔細觀察的話，可以發(fā)現(xiàn)先序左子樹區(qū)間的第一個數(shù)字2，在后序左右子樹區(qū)間的最后一個位置，而且這個規(guī)律對右子樹區(qū)間同樣適用，這是為啥呢，這就要回到各自遍歷的順序了，先序遍歷的順序是 根->左->右，而后序遍歷的順序是 左->右->根，其實這個2就是左子樹的根結(jié)點，當然會一個在開頭，一個在末尾了。發(fā)現(xiàn)了這個規(guī)律，就可以根據(jù)其來定位左右子樹區(qū)間的位置范圍了。既然要拆分數(shù)組，那么就有兩種方式，一種是真的拆分成小的子數(shù)組，另一種是用雙指針來指向子區(qū)間的開頭和末尾。前一種方法無疑會有大量的數(shù)組拷貝，不是很高效，所以我們這里采用第二種方法來做。用 preL 和 preR 分別表示左子樹區(qū)間的開頭和結(jié)尾位置，postL 和 postR 表示右子樹區(qū)間的開頭和結(jié)尾位置，那么若 preL 大于 preR 或者 postL 大于 postR 的時候，說明已經(jīng)不存在子樹區(qū)間，直接返回空指針。然后要先新建當前樹的根結(jié)點，就通過 pre[preL] 取到即可，接下來要找左子樹的根結(jié)點在 post 中的位置，最簡單的方法就是遍歷 post 中的區(qū)間 [postL, postR]，找到其位置 idx，然后根據(jù)這個 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é)點在 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;
    }
};

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

解法四：

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

以上就是“C++如何實現(xiàn)由先序和后序建立二叉樹”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。