题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
map<int,int>mp;//记录中序遍历的位置，用空间换时间
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
for(int i=0;i<vin.size();i++){
mp[vin[i]]=i;
}
return dfs(pre,vin,0,pre.size()-1,0,vin.size()-1);
}
TreeNode* dfs(vector<int> pre,vector<int> vin,int l1,int r1,int l2,int r2){
if(l1>r1)return NULL;//当两区间中没有数字，说明遍历完了
TreeNode* root=new TreeNode(pre[l1]);//创建根结点
int mid=mp[pre[l1]]-l2;//相对根节点，记得减l2,容易错
root->left=dfs(pre,vin,l1+1,l1+mid,l2,l2+mid-1);
root->right=dfs(pre,vin,l1+mid+1,r1,l2+mid+1,r2);
return root;
}
};
投递美团等公司8个岗位