Medium

Construct Binary Tree from Preorder and Postorder Traversal

LAB

Build one valid binary tree from preorder and postorder traversals and return its level-order encoding using -100000 for null gaps.

EXAMPLES

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
]

FUNCTION SHAPE

preorder: intArraypostorder: intArray→intArray

SOLUTION NOTE

Preorder = [root, L, R]. Postorder = [L, R, root]. The second preorder element is left subtree's root. Find it in postorder to split left/right subtrees.

Reveal reference solution +

pythonREFERENCE

def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
    post_idx = {v: i for i, v in enumerate(postorder)}
    pre_index = 0

    def build(post_left, post_right):
        nonlocal pre_index
        if post_left > post_right:
            return None

        root = TreeNode(preorder[pre_index])
        pre_index += 1

        if post_left == post_right:
            return root

        # Next preorder element is left child's root
        left_root = preorder[pre_index]
        left_end = post_idx[left_root]

        root.left = build(post_left, left_end)
        root.right = build(left_end + 1, post_right - 1)

        return root

    return build(0, len(postorder) - 1)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗