Recursive cpp solution


  • 0
    C
    class Solution {
    public:
        // [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)
                    break;
                    
            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.