讨论/《图解算法数据结构》 - 剑指 Offer 07. 重建二叉树/
《图解算法数据结构》 - 剑指 Offer 07. 重建二叉树

非常笨的方法
官网用了unordered_map保存index和数值的方法,优化快好多啊

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int prelength=preorder.size();
        int inlength=inorder.size();
        if(prelength!= inlength) return NULL;
        if(prelength==0)return NULL;

        int r=findroot(preorder,inorder);

        vector<int> leftpreorder; 
        vector<int> leftinorder;
        vector<int> rightpreorder; 
        vector<int> rightinorder;

        for(int i=0;i<prelength;i++){
            if(i<r) leftinorder.push_back(inorder[i]);
            if(i>r) rightinorder.push_back(inorder[i]);
            if(i>0&& i<r+1) leftpreorder.push_back(preorder[i]);
            if(i>r) rightpreorder.push_back(preorder[i]);
         }

        TreeNode *root=new TreeNode(preorder[0]);
        root->left=buildTree(leftpreorder,leftinorder);
        root->right=buildTree(rightpreorder,rightinorder);

        return root;
    }

private:
    int findroot(vector<int>& preorder, vector<int>& inorder){
        int i=0;
        for(;i<inorder.size();i++)
            if(inorder[i]==preorder[0]) break;
        return i;
    }

};
展开全部 5 讨论