这道题算是二叉树里面的基础题、经典问题了。
解决这道题,需要知道二叉树的递归定义。二叉树的前序遍历、中序遍历的性质,并用这个性质建树。
注:
- 必须要有中序遍历。
- 编号的数字不能重复。
/**
* 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return create(0,n-1,0,n-1,preorder,inorder);
}
TreeNode* create(int preL,int preR,int inL,int inR,vector<int>& preorder, vector<int>& inorder){
if(preL>preR){
return nullptr;
}
int val = preorder[preL];
TreeNode* node = new TreeNode(val);
int idx = 0;
for(int i=inL;i<=inR;i++){
if(inorder[i]==val){
idx = i;
break;
}
}
int numLeft = idx-inL;
node->left = create(preL+1,preL+numLeft,inL,idx-1,preorder,inorder);
node->right = create(preL+numLeft+1,preR,idx+1,inR,preorder,inorder);
return node;
}
};