Recursive cpp solution

  • 0
    class Solution {
        // [start, end)
        TreeNode *buildTree_helper(const vector<int>& preorder, int pre_start_idx, int pre_end_idx,
                                   const vector<int>& inorder, int in_start_idx, int in_end_idx)
            if(in_end_idx <= in_start_idx) return NULL;
            TreeNode *root = new TreeNode(preorder[pre_start_idx]);
            // find root in inorder
            int root_inorder_idx = in_start_idx;
            for(; root_inorder_idx < in_end_idx; root_inorder_idx++)
                if(inorder[root_inorder_idx] == root->val)
            root->left = buildTree_helper(preorder, pre_start_idx+1, pre_start_idx+1 + root_inorder_idx-in_start_idx,
                                          inorder, in_start_idx, root_inorder_idx);
            root->right = buildTree_helper(preorder, pre_start_idx+1 + root_inorder_idx-in_start_idx, pre_end_idx,
                                           inorder, root_inorder_idx+1, in_end_idx);
            return root;
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
            return buildTree_helper(preorder, 0, preorder.size(),
                                    inorder, 0, inorder.size());

Log in to reply

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