| 23 | return build_subtree(0, len(inorder) - 1, preorder, inorder) |
| 24 | |
| 25 | def build_subtree(left: int, right: int, preorder: List[int], inorder: List[int]) -> TreeNode: |
| 26 | global preorder_index, inorder_indexes_map |
| 27 | # Base case: if no elements are in this range, return None. |
| 28 | if left > right: |
| 29 | return None |
| 30 | val = preorder[preorder_index] |
| 31 | # Set 'inorder_index' to the index of the same value pointed at by |
| 32 | # 'preorder_index'. |
| 33 | inorder_index = inorder_indexes_map[val] |
| 34 | node = TreeNode(val) |
| 35 | # Advance 'preorder_index' so it points to the value of the next |
| 36 | # node to be created. |
| 37 | preorder_index += 1 |
| 38 | # Build the left and right subtrees and connect them to the current |
| 39 | # node. |
| 40 | node.left = build_subtree( |
| 41 | left, inorder_index - 1, preorder, inorder |
| 42 | ) |
| 43 | node.right = build_subtree( |
| 44 | inorder_index + 1, right, preorder, inorder |
| 45 | ) |
| 46 | return node |