40ms C++ code using recursion


  • 0
    J
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(!preorder.size()) return NULL;
        TreeNode* root = new TreeNode(preorder[0]);
        buildTree2(root, preorder, inorder, 0, (int)preorder.size()-1, 0, (int)inorder.size()-1);
        return root;
    }
    
    
    void buildTree2(TreeNode* root,vector<int>& preorder, vector<int>& inorder, int p_s, int p_e, int i_s, int i_e) {
        int i = i_s;
        while(inorder[i]!=root->val)
            i++;
        if (i>i_s) {
            TreeNode* left = new TreeNode(preorder[p_s+1]);
            root->left = left;
            buildTree2(root->left, preorder, inorder,p_s+1,p_s+i-i_s,i_s,i-1);
        }
        if (i<i_e) {
            TreeNode* right = new TreeNode(preorder[p_s+i-i_s+1]);
            root->right = right;
            buildTree2(root->right, preorder, inorder, p_s+i-i_s+1,p_e,i+1,i_e);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.