問題描述
返回與給定的前序和后序遍歷匹配的任何二叉樹。
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 的排列
- 每個(gè)輸入保證至少有一個(gè)答案。如果有多個(gè)答案估蹄，可以返回其中一個(gè)饿凛。
題目鏈接：889. 根據(jù)前序和后序遍歷構(gòu)造二叉樹 (難度:中等)
思路
在樹的四序遍歷當(dāng)中，先序昼丑、后序和層序能夠提供樹中節(jié)點(diǎn)的父子關(guān)系，而中序則能夠提供樹中節(jié)點(diǎn)的左右關(guān)系夸赫，因此菩帝，只有中序+先序、中序+后序茬腿、中序+層序能夠唯一確定一棵樹呼奢，而先序+后序可以確定的樹不唯一。當(dāng)答案不唯一時(shí)切平，由于后序順序?yàn)?LRN握础，先序順序?yàn)?NLR，當(dāng)某個(gè)節(jié)點(diǎn)只有一個(gè)孩子時(shí)悴品，無法從序列中確定是左子樹還是右子樹弓候，為了方便起見郎哭，我們統(tǒng)一將其定義為左子樹
對于這個(gè)問題采取分治法他匪，先確定根節(jié)點(diǎn)菇存，然后將序列分割為左右子樹的序列，各個(gè)擊破即可邦蜜。在實(shí)現(xiàn)上依鸥，使用了 unordered_map 對序列進(jìn)行緩存，既可以提高遞歸時(shí)的查找效率悼沈，同時(shí)也避免了查找過程當(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
