【剑指offer】07 重建二叉树

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;
    }
};
上一篇:Photoshop为外景人物图片调制出唯美的冬季冷调阳光色


下一篇:windows下安装RabbitMQ消息服务器