C++ recursive solution with iterator

  • 0

    A recursive solution with iterator api

    class Solution {
        using iter = std::vector<int>::iterator;
        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.