Construct Binary Tree from Preorder and Postorder Traversal LeetCode solution in Python

1
class Solution:
2
    def constructFromPrePost(
3
        self, preorder: List[int], postorder: List[int]
4
    ) -> Optional[TreeNode]:
5

6
        def build(preorder, preStart, preEnd, postorder, postStart, postEnd):
7
            if preStart > preEnd:
8
                return
9
            elif preStart == preEnd:
10
                return TreeNode(preorder[preStart])
11

12
            rootVal = preorder[preStart]
13
            leftRootVal = preorder[preStart + 1]
14
            index = valToIndex[leftRootVal]
15
            root = TreeNode(rootVal)
16
            leftSize = index - postStart + 1
17

18
            root.left = build(
19
                preorder, preStart + 1, preStart + leftSize, postorder, postStart, index
20
            )
21
            root.right = build(
22
                preorder,
23
                preStart + leftSize + 1,
24
                preEnd,
25
                postorder,
26
                index + 1,
27
                postEnd - 1,
28
            )
29

30
            return root
31

32
        valToIndex = {}
33
        for i in range(len(postorder)):
34
            valToIndex[postorder[i]] = i
35

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