0106-construct-binary-tree-from-inorder-and-postorder-traversal¶
Try it on leetcode
Description¶
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1] Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Solution(Python)¶
# 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 buildTree(self, inorder: list[int], postorder: list[int]) -> TreeNode | None:
# inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
# inroderStart_val = 3
# cur_root_idx = 4
# [ left .. is_dx - 1 ] 9
# [is_dx + 1 ... n] 15 20 7
# Node(3)
# left -> inroderStart_val = value @ inroderStart_val_idx - 1 9
# right -> cur_root_idx = value @ cur_root_idx -1 20
#
#
inorder_idx = {val: i for i, val in enumerate(inorder)}
n = len(postorder)
post_idx = n - 1
def build(left, right):
nonlocal post_idx
if left > right:
return None
node_val = postorder[post_idx]
post_idx -= 1
node = TreeNode(node_val)
mid = inorder_idx[node_val]
node.right = build(mid + 1, right)
node.left = build(left, mid -1)
return node
return build(0, n-1)