題目描述
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
參考
復(fù)雜度
時(shí)間：n*logn ?? 如果算上在中序查找根的時(shí)間的話
空間：遞歸棾尾剑空間n
迭代版見(jiàn)參考中題解模塊
思路
#:根 *：左子樹(shù)元素 ?:右子樹(shù)元素
# ***** ?????
***** # ?????
如上圖芭梯，根據(jù)前序首元素在中序中的位置，可以確定中序的左右子樹(shù)我衬，及長(zhǎng)度亡资，從而確定子樹(shù)前序中序區(qū)間嫂用，遞歸構(gòu)造
代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* digui(vector<int>& pv, vector<int>& iv,int p1,int p2,int len){
// cout<<"p1:"<<p1<<" p2:"<<p2<<" len:"<<len<<endl;
if(len==0){
return nullptr;
}
TreeNode *node=new TreeNode(pv[p1]);
if(len==1){
return node;
}
int mi=-1;
for(int i=0;i<len;i++){
// cout<<i<<"*"<<iv[p2+i]<<"*"<<pv[p1]<<endl;
if(iv[p2+i]==pv[p1]){
mi=p2+i;
break;
}
}
// cout<<"ffff:"<<mi<<endl;
int llen=mi-p2,rlen=p2+len-mi-1;
node->left=digui(pv,iv,p1+1,mi-llen,llen);
node->right=digui(pv,iv,p1+llen+1,mi+1,rlen);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int p1=0,p2=0;
int n=preorder.size();
return digui(preorder,inorder,p1,p2,n);
}
};
