Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal (Python)

Related Topic

Depth-First-Search. Tree. Postorder-Traversal. Inorder-Traversal.

Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Sample I/O

For example, given

Example 1

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Methodology

This question can be solved by Depth First Search and it is similar with question 105. Construct Binary Tree from Preorder and Inorder Traversal. The only difference is now give the postorder instead of preorder. Same method will not explain here.

Code

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder:
            return None
        root = postorder[-1]
        inorder_root_index = inorder.index(root)
        left_inorder = inorder[:inorder_root_index]
        right_inorder = inorder[inorder_root_index+1:]
        left_postorder = postorder[:inorder_root_index]
        right_postorder = postorder[inorder_root_index:-1]
        root = TreeNode(root)
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)
        return root

BigO

We go through both postorder list and inorder list, so the total time complexity is O(2n)