Simple O(N) iterative solution without recursion


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode* createTreeNode(int val, TreeNode* left, TreeNode* right){
    
    TreeNode* node = new TreeNode(val);
    node->left = left;
    node->right = right;
    
    return node;
}

TreeNode* takeTopAndRemove(stack<TreeNode*> &skipped){
    TreeNode* node = skipped.top();
    skipped.pop();
    
    return node;
}

TreeNode* Solution::buildTree(vector<int> &preOrder, vector<int> &inOrder) {
    
    int N = inOrder.size();
    
    stack<TreeNode*> skipped;
    TreeNode* root = NULL;
    
    int i = N - 1;
    int j = N - 1;
    
    while(i >= 0){
        
        if(skipped.size() > 0 && skipped.top()->val == preOrder[i])
        {
            TreeNode* node = takeTopAndRemove(skipped);
            node->left = root;
            root = node;
            
            i--;
            continue;
        } 
        
        if(j < 0)
            throw "This code shouldn't be reached";
        
        if(preOrder[i] == inOrder[j])
        {
            TreeNode* newNode = createTreeNode(preOrder[i], NULL, root);
            root = newNode;
            
            i--;
        }
        else
        {
            TreeNode* newNode = createTreeNode(inOrder[j], NULL, root);
            root = NULL;
            
            skipped.push(newNode);
        }
        
        j--;
    }
    
    return root;
}