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;
    }
};