#889

Construct Binary Tree from Preorder and Postorder Traversal

pupil · 460 · lc medium +26 · failed · 78.1% accepted · 3,387 likes · top 89%

Description

Given two integer arrays preorder and postorder where preorder is the pre-order traversal and postorder is the post-order traversal of a binary tree with distinct values, reconstruct and return the binary tree.

If more than one valid tree exists, return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]

Output: [1]

Code

# 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
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

# 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
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]: