Construct Binary Tree from Inorder and Postorder Traversal

Problem: Construct Binary Tree from Inorder and Postorder Traversal

We can learn how to define tree traversals from Wikipedia. We can see that the last element of postorder is root of the tree and elements of right subtree are always after elements of left subtree. We can access root from postorder and use that to split inorder traversal into left and right subtree. Then we construct right subtree from the same postorder and corresponding inorder and do left subtree at last.

Code in Python:

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return None
        cur = postorder.pop()
        node = TreeNode(cur)
        k = inorder.index(cur)
        node.right = self.buildTree(inorder[k+1:], postorder)
        node.left = self.buildTree(inorder[:k], postorder)
        return node