C++ recursive solution with iterator


  • 0
    Y

    A recursive solution with iterator api

    class Solution {
    public:
        using iter = std::vector<int>::iterator;
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
        {
            return buildTreeHelper(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
        }
        
        TreeNode* buildTreeHelper(iter inOrderBegin, iter inOrderEnd, iter postOrderBegin, iter postOrderEnd)
        {
            if (inOrderBegin == inOrderEnd)
                return nullptr;
            if (std::next(inOrderBegin) == inOrderEnd)
                return new TreeNode(*inOrderBegin);
            TreeNode *root = new TreeNode(*std::prev(postOrderEnd));
            auto pivot = std::find(inOrderBegin, inOrderEnd, root->val);
            auto leftSize = std::distance(inOrderBegin, pivot);
            auto rightSize = std::distance(pivot, inOrderEnd) - 1;
            if (leftSize != 0)
                root->left = buildTreeHelper(inOrderBegin, pivot, postOrderBegin, std::next(postOrderBegin, leftSize));
            if (rightSize != 0)
                root->right = buildTreeHelper(std::next(pivot), inOrderEnd, std::next(postOrderBegin, leftSize), std::prev(postOrderEnd));
            return root;
        }
    };
    

Log in to reply
 

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