07 重建二叉树
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
思考
- 一开始以为只能在leetcode给的那个函数里面实现，不能另开函数，一直想不出不用递归来实现的方法，然后看到好像可以递归，然后，就递归咯
- 主要是利用preorder的第一个值作为root在inorder中确定位置，那么inorder左边的便是左子树，右边的便是右子树。递归实现左右子树即可。
- 因为不含重复的数字，因此我一开始是每次要确定在inorder中的位置就全部遍历一遍，果不其然，时间很长很长
- 然后看到别人说用map可以提升速度，果然！！！快了超多，所以对于这种总是遍历的，用STL可能会快很多。
代码
/**
* 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 {
map<int,int> dic;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0;i<inorder.size();i++)
dic[inorder[i]] = i;
return build(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}
TreeNode* build(vector<int>& preorder, vector<int> & inorder, int ps,int pe, int is, int ie){
if(ps>=pe||is>=ie) return NULL;
TreeNode * ret = new TreeNode;
ret->val = preorder[ps];
// 这里使用了map
int index = dic[preorder[ps]];
int dif = index-is;
ret->left = build(preorder,inorder,ps+1,ps+index-is+1,is,index);
ret->right = build(preorder, inorder,ps+index-is+1,pe,index+1,ie);
return ret;
}
};