目錄
題目來源
解題方法
DFS
/**
* 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 {
unordered_map<int,int> map;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size();
for(int i=0;i<n;i++){
map[inorder[i]]=i;
}
return helper(preorder,inorder,0,n-1,0,n-1);
}
TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pre_start,int pre_end,int in_start,int in_end){
if(pre_start>pre_end)
return NULL;
TreeNode* root;
root = new TreeNode(preorder[pre_start]);
int index=map[preorder[pre_start]];
int left_num=index-in_start;
root->left=helper(preorder, inorder, pre_start+1,pre_start+left_num,in_start,index-1);
root->right=helper(preorder, inorder, pre_start+left_num+1, pre_end, index+1,in_end);
return root;
}
};