從前序中序周遊或中序後序周遊恢複二叉樹 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//劍指Offer 第2版 64頁
if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
TreeNode* build(vector<int>& preorder, int preorder_begin, int preorder_end, vector<int>& inorder, int inorder_begin, int inorder_end){
//前序周遊第一個元素是根節點
TreeNode* root = new TreeNode(preorder[preorder_begin]);
//截止條件
if(preorder_begin == preorder_end) return root;
//根據根節點的值在中序周遊中劃分出左子樹和右子樹
int root_inorder = inorder_begin;
for(; root_inorder <= inorder_end; root_inorder++){
if(preorder[preorder_begin] == inorder[root_inorder]){
break;
}
}
//if(root_inorder == inorder.size()) //沒有找到根節點
int leftlength = root_inorder - inorder_begin;
int leftpreorderend = preorder_begin + leftlength;
//根據中序周遊的劃分出的左右子樹,更新preorder_begin,preorder_end,inorder_begin,inorder_end
if(leftlength > 0){
root->left = build(preorder,preorder_begin + 1,leftpreorderend, inorder, inorder_begin, root_inorder-1);
}
if(inorder_end - root_inorder > 0){
root->right = build(preorder,leftpreorderend+1,preorder_end, inorder, root_inorder+1, inorder_end);
}
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size() == 0 || postorder.size() == 0) return nullptr;
return build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
}
TreeNode* build(vector<int>& inorder, int inorder_begin, int inorder_end, vector<int>& postorder, int postorder_begin, int postorder_end){
if(inorder_begin > inorder_end || postorder_begin > postorder_end) return nullptr;
//找到根節點
TreeNode* root = new TreeNode(postorder[postorder_end]);
//if(inorder_begin == inorder_end) return root;
int root_pos = inorder_begin;
for(;root_pos<=inorder_end;root_pos++){
if(inorder[root_pos] == postorder[postorder_end])
{
break;
}
}
int left_len = root_pos - inorder_begin;
root->left = build(inorder, inorder_begin, inorder_begin + left_len - 1,postorder, postorder_begin, postorder_begin + left_len - 1);
root->right = build(inorder, root_pos + 1, inorder_end, postorder, postorder_begin+left_len,postorder_end-1);
return root;
}