O(N) solution with forward iteration
The code makes sure each step we are in the state where\n\n 1. We have a constructed sub tree. (the "working" tree in the code)\n 1. Both iterators point to jus
The code makes sure each step we are in the state where\n\n 1. We have a constructed sub tree. (the "working" tree in the code)\n 1. Both iterators point to just pass that subtree. (the nodes for the subtree are continuous in both in-order and post-order lists.)\n\nThen, we can deduce that: **the next node in the in-order list must be the parent of the working tree**.\n\n 1. We extend the working tree by adding the next in-order list node as its parent, then push it to a stack; clear the working tree, and work on building the right branch from scratch. **All the notes until the same node appears in post-order are for the right child of the parent.**\n 1. When the post-order element matches with the stack top, then the stack top node has its right branch finished. Thus, pop the stack, make the working tree as its right child. Point the working tree to the new completed tree.\n\nRun this over until the postorder sequences are consumed. The working tree is the answer, and the stack at that point should be empty.\n\nHere's the code\n\n    class Solution {\n     public:\n      TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        if (inorder.empty()) return nullptr;\n        // 'parents' contains all the nodes we have seen so far, we haven't\n        // finished building their right branch nodes yet.\n        vector<TreeNode*> parents;\n        // 'working' is a completed subtree of the final problem, based on the\n        // inorder/postorder we examined so far. We will keep adding its parent to\n        // build the final tree.\n        TreeNode* working = nullptr;\n        auto in = inorder.begin();\n        auto post = postorder.begin();\n        while (post != postorder.end())  {\n          if (!parents.empty() && *post == parents.back()->val) {\n            // Post order node matches the stack top parent notes. It means the\n            // working tree is the right branch of the stack top. Pop the stack top\n            // to be the working tree.\n            parents.back()->right = working;\n            working = parents.back();\n            parents.pop_back();\n            ++post;\n          } else {\n            // Otherwise, we get a new parent for the current working tree. \n            // Extend the existing working tree, push it to the stack and work on\n            // the right branch of the new parent.\n            TreeNode* new_node = new TreeNode(*in);\n            new_node->left = working;\n            working = nullptr;\n            parents.push_back(new_node);\n            ++in;\n          }\n        }\n        return working;\n      }\n    };
[]