Python solution
We illustrate the algorithm with an example. Consider inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]. Since, we know that postorder traversal traverses a tr
We illustrate the algorithm with an example. Consider `inorder = [9,3,15,20,7]`, `postorder = [9,15,7,20,3]`. Since, we know that postorder traversal traverses a tree in the order `left subtree -> right subtree -> root`, and inorder traversal traverses a tree in the order `left subtree -> root -> right subtree`, `3` must be thre root of the tree, and values that come after (before) `3` in `inorder` must be in the right (left) subtree of `3`. Repeating the above procedure recursively until each subtree consists of a single node, we finish constructing the whole tree. For example, the right subtree of the root `3` consists of values `15`, `20`, `7`. Furthermore, since `20` comes right after `3` when traversing `postorder` from the right, it is the root of the right subtree of `3`. Finally, since `15` (`7`) comes before (after) `20` in `inorder`, it is the left (right) child of `20`. The same analysis applies to the left subtree of `3`, and the binary tree is given by `3(9)(20(15)(7))`.\n\nWe can implement the above algorithm in an iterative fashion. To do this, we first construct a hashmap `idx` which maps a value to its inorder index. This will give us an `O(1)` look up of the inorder indices of values of a root and its child, so that we can decide if the child is a left child or right child of the root. Then we can construct the tree with the help of a `stack`. We iterate over `postorder` from the right and create a TreeNode `node` with the corresponding value `val`. If the head is null, we let `head = node`, and push `head` into the `stack`. Else, if the inorder index `stack[-1]` is smaller than that of `val`, we assign `stack[-1].right = node`, and push `node` into the `stack`. Otherwise, we pop from `stack` to until either `stack` is empty or the inorder index of `stack[-1]` is smaller than that of `node`. We assign `u.left = node` for the last popped node `u` from `stack`, and then push `node` to `stack`. After iterating over `postorder`, we return `head`. \n\nTime complexity: `O(n)`, space complexity: `O(n)`.\n\n```\nclass Solution(object):\n    def buildTree(self, inorder, postorder):\n        """\n        :type inorder: List[int]\n        :type postorder: List[int]\n        :rtype: TreeNode\n        """\n        idx = {}\n        for i, val in enumerate(inorder):\n            idx[val] = i\n        \n        head = None\n        stack = []\n        for i in range(len(postorder)-1, -1, -1):\n            val = postorder[i]\n            if not head:\n                head = TreeNode(val)\n                stack.append(head)\n            else:\n                node = TreeNode(val)\n                if idx[val] > idx[stack[-1].val]:\n                    stack[-1].right = node\n                else:\n                    while stack and idx[stack[-1].val] > idx[val]:\n                        u = stack.pop()\n                    u.left = node\n                stack.append(node)\n        return head\n```
[]