105. Construct Binary Tree from Preorder and Inorder Traversal

class Solution
{
private:
    vector<int> preorderTraversal;
    vector<int> inorderTraversal;

    // right means the last valid item
    TreeNode* buildTree(int preLeft, int preRight, int inLeft, int inRight)
    {
        if(preLeft > preRight || inLeft > inRight) return nullptr;

        TreeNode *result = new TreeNode(preorderTraversal[preLeft]);

        int inorderRootIndex = find(inorderTraversal.begin(), inorderTraversal.end(), preorderTraversal[preLeft]) - inorderTraversal.begin();
        int leftChildNodesCount = inorderRootIndex - inLeft;
        int rightChildNodesCount = inRight - inorderRootIndex;

        result->left = buildTree(preLeft + 1, preLeft + leftChildNodesCount, inLeft, inorderRootIndex - 1);
        result->right = buildTree(preRight - rightChildNodesCount + 1, preRight, inorderRootIndex + 1, inRight);

        return result;
    }
public:
    // TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    TreeNode* buildTree(const vector<int> &i_preorderTraversal, vector<int> &i_inorderTraversal)
    {
        preorderTraversal = i_preorderTraversal;
        inorderTraversal = i_inorderTraversal;

        return buildTree(0, preorderTraversal.size() - 1, 0, inorderTraversal.size() - 1);
    } 
};

// the iteration method is pretty hard 🥺, I learn it from the Leetcode(Chinese)
// for any insecutive two nodes A and B in preorder, they only have two possible relationships
// 1. A is the parent of B, while B is the left child of A
// 2. A doesn't have left child, while B is the right child of one parent of A(or it self)

class Solution 
{
public:
    // TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    TreeNode* buildTree(const vector<int> &i_preorderTraversal, vector<int> &i_inorderTraversal) 
    {
        // Leetcode usually don't give vicious inputs and they will give constranints or notes to ensure that
        // but this time, they don't say preorder array and inorder array will have same count nodes
        if(i_preorderTraversal.size() != i_inorderTraversal.size() || i_preorderTraversal.empty()) return nullptr;
        
        TreeNode *result = new TreeNode(i_preorderTraversal.front());
        // the stack means parent nodes, which don't consider right child for now
        stack<TreeNode*> nodesNotCheckRightChild{{result}};

        for(int i = 1, index = 0; i < i_preorderTraversal.size(); i++)
        {
            int preorderValue = i_preorderTraversal[i];
            TreeNode *node = nodesNotCheckRightChild.top();
            
            // this case means the current node is the stack.top() node's left child
            // since preorder is root->left->right, inorder is left->root->right
            // if two secutive nodes A and B, B is A's right child, then A doesn't have left child
            // in this case, two orders are root->right, so they must be equal
            if(node->val != i_inorderTraversal[index]) 
            {
                node->left = new TreeNode(preorderValue);
                nodesNotCheckRightChild.push(node->left);
            }
            else
            {
                // this case means left single branch, so two orders are reverse
                while(!nodesNotCheckRightChild.empty() && nodesNotCheckRightChild.top()->val == i_inorderTraversal[index])
                {
                    node = nodesNotCheckRightChild.top();
                    nodesNotCheckRightChild.pop();
                    index++;
                }
                
                node->right = new TreeNode(preorderValue);
                nodesNotCheckRightChild.push(node->right);
            }
        }
        
        return result;
    }
};