72ms C++ Solution with iterator


  • 0
    S
    class Solution {
    typedef vector<int>::iterator It;
    TreeNode* buildTreeHelper(It preStart, It preEnd, It inStart, It inEnd) {
        if (distance(preStart, preEnd) != distance(inStart, inEnd)) {
            throw runtime_error("Invaild input.");
        }
        if (distance(preStart, preEnd) == 0) {
            return NULL;
        }
        auto head = *preStart;
        auto headInInorder = std::find(inStart, inEnd, head);
        if (headInInorder == inEnd) {
            throw runtime_error("Cannot find head in inorder list.");
        }
        int leftTreeSize = distance(inStart, headInInorder);
    
        TreeNode *currNode = new TreeNode(head);
        currNode->left = buildTreeHelper(next(preStart), next(preStart, 1 + leftTreeSize), inStart, next(inStart, leftTreeSize));
        currNode->right = buildTreeHelper(next(preStart, 1 + leftTreeSize), preEnd, next(inStart, 1 + leftTreeSize), inEnd);
        return currNode;
    
    }
    public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeHelper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
    

    };


Log in to reply
 

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