Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
-------------------------------- codes ---------------------------------------------------
 class Solution {
 public:
     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
         if (inorder.size() == 0) {
             return NULL;
         }
         int pp = postorder.size() - 1;
         int pi = inorder.size() - 1;
         stack<TreeNode*> stack;
         TreeNode *root = new TreeNode(postorder[pp--]);
         stack.push(root);
         while (true) {
             //bug here, the end of looping should be at pi < 0, instead of pp or stack.size()
             if (stack.top()->val == inorder[pi]) {
                 pi--;
                 if (pi < 0) break;
                 TreeNode *cur = stack.top();
                 stack.pop();
                 //bug here, stack.size() should also be considered because it is possible that stack is temporally empty
                 if (stack.size() > 0 && stack.top()->val == inorder[pi]) {
                     continue;
                 }
                 TreeNode *ele = new TreeNode(postorder[pp]);
                 pp--;
                 cur->left = ele;
                 stack.push(ele);
             } else {
                 TreeNode *ele = new TreeNode(postorder[pp]);
                 pp--;
                 stack.top()->right = ele;
                 stack.push(ele);
             }
         }
         return root;
     }
 };

---------------------------------- read for iterative method --------------------------

https://oj.leetcode.com/discuss/23834/java-iterative-solution-with-explanation
public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder.length == 0 || postorder.length == 0) return null; int ip = inorder.length - 1; int pp = postorder.length - 1; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode prev = null; TreeNode root = new TreeNode(postorder[pp]); stack.push(root); pp--; while (pp >= 0) { while (!stack.isEmpty() && stack.peek().val == inorder[ip]) { prev = stack.pop(); ip--; } TreeNode newNode = new TreeNode(postorder[pp]); if (prev != null) { prev.left = newNode; } else if (!stack.isEmpty()) { TreeNode currTop = stack.peek(); currTop.right = newNode; } stack.push(newNode); prev = null; pp--; } return root; }

This is my iterative solution, think about "Constructing Binary Tree from inorder and preorder array", the idea is quite similar. Instead of scanning the preorder array from beginning to end and using inorder array as a kind of mark, in this question, the key point is to scanning the postorder array from end to beginning and also use inorder array from end to beginning as a mark because the logic is more clear in this way. The core idea is: Starting from the last element of the postorder and inorder array, we put elements from postorder array to a stack and each one is the right child of the last one until an element in postorder array is equal to the element on the inorder array. Then, we pop as many as elements we can from the stack and decrease the mark in inorder array until the peek() element is not equal to the mark value or the stack is empty. Then, the new element that we are gonna scan from postorder array is the left child of the last element we have popped out from the stack.

https://oj.leetcode.com/discuss/15115/my-comprehension-of-o-n-solution-from-%40hongzhi

Below is the O(n) solution from @hongzhi but that discuss is closed now 'cause @hongzhi says little about his code.

https://oj.leetcode.com/discuss/6334/here-is-my-o-n-solution-is-it-neat

I've modified some of and tried this code and got AC. Just share about some comprehension about his code.

I've modified vtn(vector) to stn(stack) in that stack is probably what this algs means and needs.

What matters most is the meaning of stn.

Only nodes whoes left side hasn't been handled will be pushed into stn.

And inorder is organized as (inorder of left) root (inorder of right),

And postorder is as (postorder of left) (postorder of right) root.

So 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.

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.

Note 2: we delete one node from postorder as we push one into stn.

Now we have [root, root's right] as stn and we check inorder.back() == stn.top()->val again.

• true means inorder.back() is the root node and needs handled left case.
• false means inorder.back() is the next right sub-node

So when we encounter a true, we will cache stn.top() as p and delete both nodes from inorder and stn.

Then we check inorder.size(), if there's no nodes left, it means p has no left node.

Else the next node in inorder could be p's left node or p's father which equals to the nowstn.top() (remember we popped p from stn above).

If the latter happens, it means p has no left node and we need to move on to p's father(stn.top()).

If 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.

That's all of it. The algs just build a binary tree. :)

Inform me if there's anything vague or wrong, I'm open to any suggestions.