106. Construct Binary Tree from Inorder and Postorder Traversal

class Solution
{
private:
    vector<int> inorder, postorder;
    
    TreeNode* buildTree(int inLeft, int inRight, int postLeft, int postRight)
    {
        if(inLeft > inRight || postLeft > postRight) return nullptr;
        
        int rootValue = postorder[postRight];
        TreeNode *result = new TreeNode(rootValue);
        
        int inorderRootIndex = find(inorder.begin() + inLeft, inorder.begin() + inRight + 1, rootValue) - inorder.begin();
        int leftChildNodesCount = inorderRootIndex - inLeft;
        int rightChildNodesCount = inRight - inorderRootIndex;
        
        result->left = buildTree(inLeft, inorderRootIndex - 1, postLeft, postLeft + leftChildNodesCount - 1);
        result->right = buildTree(inorderRootIndex + 1, inRight, postRight - rightChildNodesCount, postRight - 1);
        
        return result;
    }
    
public:
    // TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    TreeNode* buildTree(const vector<int> &i_inorder, const vector<int> &i_postorder)
    {
        inorder = i_inorder;
        postorder = i_postorder;
        
        return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);
    }
}

// the iteration method is pretty hard 🥺, I learn it from the Leetcode(Chinese)

class Solution 
{
public:
    // TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    TreeNode* buildTree(const vector<int> &i_inorder, const vector<int> &i_postorder) 
    {
        if(i_inorder.size() != i_postorder.size() || i_inorder.empty()) return nullptr;
        
        TreeNode *result = new TreeNode(i_postorder.back());
        stack<TreeNode *> nodesNotCheckLeftChild{{result}};
        
        for(int i = i_postorder.size() - 2, index = i_inorder.size() - 1; i >= 0; i--)
        {
            int postorderValue = i_postorder[i];
            auto node = nodesNotCheckLeftChild.top();
            
            if(node->val != i_inorder[index])
            {
                node->right = new TreeNode(postorderValue);
                nodesNotCheckLeftChild.push(node->right);
            }
            else
            {
                while(!nodesNotCheckLeftChild.empty() && nodesNotCheckLeftChild.top()->val == i_inorder[index])
                {
                    node = nodesNotCheckLeftChild.top();
                    nodesNotCheckLeftChild.pop();
                    index--;
                }
                
                node->left = new TreeNode(postorderValue);
                nodesNotCheckLeftChild.push(node->left);
            }
        }
        
        return result;
    }
};