My comprehension of O(n) solution from @hongzhi
Below is the O(n) solution from @hongzhi but that discuss is closed now 'cause @hongzhi says little about his code. \n\nhttps://oj.leetcode.com/discuss/6334/her
Below is the O(n) solution from @hongzhi but that discuss is closed now 'cause @hongzhi says little about his code. \n\nhttps://oj.leetcode.com/discuss/6334/here-is-my-o-n-solution-is-it-neat\n\nI've modified some of and tried this code and got AC.\nJust share about some comprehension about his code.\n\nI've modified vtn(vector) to stn(stack) in that **stack** is probably what this algs means and needs.\n\nWhat matters most is the meaning of *stn*. \n\nOnly nodes whoes left side **hasn't been** handled will be pushed into *stn*.\n\nAnd inorder is organized as (inorder of left) root (inorder of right),\n\nAnd postorder is as (postorder of left) (postorder of right) root.\n\nSo at the very begin, we only have root in stn and we check if *inorder.back() == root->val* and in most cases it's **false**(see Note 1). Then we make this node root's right sub-node and push it into stn. \n\n**Note 1: this is actually *(inorder of right).back() == (postorder of right).back()*, so if only there's no right subtree or the answer will always be false.**\n\n**Note 2: we delete one node from *postorder* as we push one into stn.**\n\nNow we have [root, root's right] as stn and we check *inorder.back() == stn.top()->val* again. \n\n - **true** means *inorder.back()* is the root node and needs handled left case.\n - **false** means *inorder.back()* is the next right sub-node\n\nSo when we encounter a true, we will cache *stn.top()* as p and **delete both nodes from inorder and stn**. \n\nThen we check inorder.size(), if there's no nodes left, it means p has no left node. \n\nElse the next node in inorder could be *p's left node* or *p's father* which equals to the now *stn.top()* (remember we popped *p* from *stn* above). \n\nIf the latter happens, it means *p* has **no left node** and we need to move on to *p's father(stn.top())*.\n\nIf the former happens, it means *p* has one left node and it's *postorder.back()*, so we put it to p's left and delete it from the *postorder* and push the left node into *stn* 'cause **it** should be the next check node as the *postorder* is organized as above.\n\nThat's all of it. The algs just build a binary tree. :)\n\nInform me if there's anything vague or wrong, I'm open to any suggestions.\n\n    class Solution {\n    public:\n        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {\n            if(inorder.size() == 0)return NULL;\n            TreeNode *p;\n            TreeNode *root;\n            stack<TreeNode *> stn;\n            \n            root = new TreeNode(postorder.back()); \n            stn.push(root); \n            postorder.pop_back(); \n            \n            while(true)\n            {\n                if(inorder.back() == stn.top()->val) \n                {\n                    p = stn.top();\n                    stn.pop(); \n                    inorder.pop_back(); \n                    if(inorder.size() == 0) break;\n                    if(stn.size() && inorder.back() == stn.top()->val)\n                        continue;\n                    p->left = new TreeNode(postorder.back()); \n                    postorder.pop_back();\n                    stn.push(p->left);\n                }\n                else \n                {\n                    p = new TreeNode(postorder.back());\n                    postorder.pop_back();\n                    stn.top()->right = p; \n                    stn.push(p); \n                }\n            }\n            return root;\n        }\n    };
[]