Recursive cpp code


  • 0
    C
    class Solution {
    public:
        // [start, end)
        TreeNode *buildTree_helper(const vector<int>& inorder, int in_start_idx, int in_end_idx,
                                   const vector<int>& postorder, int post_start_idx, int post_end_idx)
        {
            if(in_end_idx <= in_start_idx) return NULL;
            
            TreeNode *root = new TreeNode(postorder[post_end_idx-1]);
            
            // 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(inorder, in_start_idx, root_inorder_idx,
                                          postorder, post_start_idx, post_start_idx + root_inorder_idx-in_start_idx);
            root->right = buildTree_helper(inorder, root_inorder_idx+1, in_end_idx,
                                           postorder, post_start_idx + root_inorder_idx-in_start_idx, post_end_idx-1);
                                           
            return root;
        }
        
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
        {
            return buildTree_helper(inorder, 0, inorder.size(),
                                    postorder, 0, postorder.size());
        }
    };

Log in to reply
 

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