Construct Binary Tree from Preorder and (#889)

lcpy gen -n 889   # by problem number
lcpy gen -s construct_binary_tree_from_preorder_and_postorder_traversal   # by problem name

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]

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

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(n)
    def construct_from_pre_post(
        self, preorder: list[int], postorder: list[int]
    ) -> TreeNode[int] | None:
        index = {value: i for i, value in enumerate(postorder)}
        self._pre_index = 0
        return self._build(preorder, index, 0, len(postorder) - 1)

    def _build(
        self, preorder: list[int], index: dict[int, int], lo: int, hi: int
    ) -> TreeNode[int] | None:
        if lo > hi:
            return None
        node = TreeNode(preorder[self._pre_index])
        self._pre_index += 1
        if lo < hi:
            left_size = index[preorder[self._pre_index]] - lo + 1
            node.left = self._build(preorder, index, lo, lo + left_size - 1)
            node.right = self._build(preorder, index, lo + left_size, hi - 1)
        return node