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.
# 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