問題描述
返回與給定的前序和后序遍歷匹配的任何二叉樹。
pre 和 post 遍歷中的值是不同的正整數(shù)。
Example
輸入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
輸出：[1,2,3,4,5,6,7]
Note
- 1 <= pre.length == post.length <= 30
- pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
- 每個輸入保證至少有一個答案。如果有多個答案，可以返回其中一個。
題目鏈接：889. 根據(jù)前序和后序遍歷構(gòu)造二叉樹 (難度:中等)
思路
在樹的四序遍歷當(dāng)中，先序、后序和層序能夠提供樹中節(jié)點的父子關(guān)系，而中序則能夠提供樹中節(jié)點的左右關(guān)系，因此，只有中序+先序、中序+后序、中序+層序能夠唯一確定一棵樹，而先序+后序可以確定的樹不唯一。當(dāng)答案不唯一時，由于后序順序為 LRN，先序順序為 NLR，當(dāng)某個節(jié)點只有一個孩子時，無法從序列中確定是左子樹還是右子樹，為了方便起見，我們統(tǒng)一將其定義為左子樹
對于這個問題采取分治法，先確定根節(jié)點，然后將序列分割為左右子樹的序列，各個擊破即可。在實現(xiàn)上，使用了 unordered_map 對序列進(jìn)行緩存，既可以提高遞歸時的查找效率，同時也避免了查找過程當(dāng)中的越界情況。具體過程可見下圖：
左右子樹同，則統(tǒng)一當(dāng)作左子樹處理
左右子樹不同，則分治處理左右子樹
代碼
class Solution {
public:
unordered_map<int, int> pre_table;
unordered_map<int, int> post_table;
TreeNode* buildTree(vector<int>& pre, int l_pre, int r_pre, vector<int>& post, int l_post, int r_post){
if(l_pre > r_pre)
return NULL;
TreeNode* root = new TreeNode(pre[l_pre]);
if(l_post == r_post){
return root;
}
int l_root = pre[l_pre + 1];
int r_root = post[r_post - 1];
if(l_root == r_root){
root->left = buildTree(pre, l_pre + 1, r_pre, post, l_post, r_post - 1);
root->right = NULL;
}else{
int r_pre_root = pre_table[r_root];
int l_post_root = post_table[l_root];
root->left = buildTree(pre, l_pre + 1, r_pre_root - 1, post, l_post, l_post_root);
root->right = buildTree(pre, r_pre_root, r_pre, post, l_post_root + 1, r_post - 1);
}
return root;
}
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
int len = pre.size();
for(int i = 0;i < len;++i){
pre_table[pre[i]] = i;
post_table[post[i]] = i;
}
return buildTree(pre, 0, len - 1, post, 0, len - 1);
}
};
執(zhí)行結(jié)果: 28ms, 27.6MB
