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.
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]
Constraints:
-
1 <= preorder.length <= 30 -
1 <= preorder[i] <= preorder.length - All the values of
preorderare unique. -
postorder.length == preorder.length -
1 <= postorder[i] <= postorder.length - All the values of
postorderare unique. - It is guaranteed that
preorderandpostorderare the preorder traversal and postorder traversal of the same binary tree.
SOLUTION:
# 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 makeTree(self, preorder, pri, prj, prepos, postorder, poi, poj, postpos):
if pri >= prj:
return None
root = TreeNode(val = preorder[pri])
if pri + 1 == prj:
return root
leftval = preorder[pri + 1]
rightval = postorder[poj - 2]
root.left = self.makeTree(preorder, pri + 1, prepos[rightval], prepos, postorder, poi, postpos[leftval] + 1, postpos)
root.right = self.makeTree(preorder, prepos[rightval], prj, prepos, postorder, postpos[leftval] + 1, poj - 1, postpos)
return root
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
n = len(preorder)
prepos = {}
postpos = {}
for i, preval in enumerate(preorder):
prepos[preval] = i
for i, postval in enumerate(postorder):
postpos[postval] = i
return self.makeTree(preorder, 0, n, prepos, postorder, 0, n, postpos)
Top comments (0)