Annotated iterative solution with comments, does not modify parameters
Courtesy of the post by lizhuogo. Details see\n    https://discuss.leetcode.com/topic/4746/my-comprehension-of-o-n-solution-from-hongzhi/2\n\nI thought his expl
Courtesy of the post by lizhuogo. Details see\n    https://discuss.leetcode.com/topic/4746/my-comprehension-of-o-n-solution-from-hongzhi/2\n\nI thought his explanation is still a bit difficult to understand so I try to give a high-level understanding of this approach and the fundamental reason why it works as intended.\n\nThe key here is knowing the patterns of serialized list of inorder and postorder\ntravesals.\n\nIf we traverse from root to the left child and back up, both inorder\nand postorder traversals give us the same sequence, i.e. they are in\nthe same direction.\n```       \n       1\n      /\n    2\ninorder:  [1, 2]\npostorder: [1, 2]\n```\nwhereas if we traverse from root to right child and back up, inorder and postorder\ngives us sequences that are reverse of each other.\n```\n     1\n      \\\n       2\ninorder: [1, 2]\npostorder: [2, 1]\n```\nUsing this observation, and the fact that the last member in postorder array is\nthe root of current subtree, we can traverse from right to left of the serialized\nlists and build left and right child accordingly.\n\nIf we see postorder and inorder are of same value, we build the left child, else\nwe build the right child. After each operation, we store the newly created node\non stack to be the new root of the current subtree of size 1 and later traverse back\nup.\n\nA stack is helpful for storing them because each pop let us go back up a level to\nthe parent of our current root.\n\nCode in Python below with comments:\n```\ndef buildTree(self, inorder, postorder):\n    if len(inorder) == 0: return None\n    root = TreeNode(postorder[-1])\n    stack = [root]   \n    # array indexes, i for inorder array, p for postorder array\n    i = len(inorder) - 1\n    p = len(postorder) - 2 # initially root already 'popped' off postorder and stored in stack\n\n    # we store values off postorder array and compare top of stack with\n    # right most member of inorder array (indexed by i)\n    while True:\n      # top of stack is same as right most entry of inorder. The first time it\n      # happens means we reached root of current tree. Then we keep removing them\n      # since we already built right child nodes with them and they are on stack just so we\n      # can traverse back up. See the else branch for the actual creation of right child. \n      if stack[-1].val == inorder[i]:\n        n = stack.pop()\n        i -= 1\n\n        if i==-1: break\n        if stack and inorder[i] == stack[-1].val:\n          # keep removing these values, that is, traverse back up\n          continue\n\n        # finished all the right branch and root itself, now we build left child\n        # 'n' here was popped from stack which gave us the current root.\n        n.left = TreeNode(postorder[p])\n        p -= 1\n        stack.append(n.left)\n\n      else: # mismatch values means we should build right child for current root\n        n = TreeNode(postorder[p])\n        p-=1\n        stack[-1].right = n\n        stack.append(n)\n        \n    return root\n```
[]