889. Construct Binary Tree from Preorder and Postorder Traversal

Description:

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

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

'''
[1] divide and conquer)

idea::
1. set root
2. divide lists based on pivot(root)
3. link it

-T/C: O(n) # O(n/2) for finding pivot index of post-list from pre-list, O(logn) for dividing
-S/C: O(logn) # function stack
'''
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(preorder)==0:
            return None
        elif len(preorder)==1:
            return TreeNode(preorder[0])
        
        # setting root
        root=TreeNode(preorder[0])
        
        # divide
        pivot_idx=postorder.index(preorder[1])
        length_left=len(postorder[0:pivot_idx+1])
        
        left_root=self.constructFromPrePost(preorder[1:length_left+1],postorder[0:length_left+1])
        right_root=self.constructFromPrePost(preorder[length_left+1:],postorder[length_left:-1])
        
        root.left=left_root
        root.right=right_root
        
        return root