Construct Binary Tree from Preorder and Postorder Traversal

Problem Id: 889 Difficulty: Medium Tag: Tree


Intuition

Since the values in the tree are distinct, for each i, j where preorder[i] == postorder[j], preorder[i:j] and postorder[i:j] are the preorder and postorder of the node preorder[i]. And if i == j, the node has no left child and right child. We could use this and solve this problem recursivly.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
        if len(pre) == 0:
            return None
        node = TreeNode(pre[0])
        if len(pre) == 1:
            return node

        l = pre[1]
        r = post[-2]
        l_i = 0
        while post[l_i] != l:
            l_i += 1
        node.left = self.constructFromPrePost(pre[1:l_i + 2], post[:l_i + 1])
        if r != l:
            node.right = self.constructFromPrePost(pre[l_i + 2:], post[l_i + 1:-1])
        return node