I'm looking at LeetCode problem: 105. Construct Binary Tree from Preorder and Inorder Traversal:
Given two integer arrays
preorderandinorderwherepreorderis the preorder traversal of a binary tree andinorderis the inorder traversal of the same tree, construct and return the binary tree.Template code:
# 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, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
I used the code that is provided in the Editorial of the challenge:
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def array_to_tree(left, right): nonlocal preorder_index # if there are no elements to construct the tree if left > right: return None # select the preorder_index element as the root and increment it root_value = preorder[preorder_index] root = TreeNode(root_value) preorder_index += 1 # build left and right subtree # excluding inorder_index_map[root_value] element because it's the root root.left = array_to_tree(left, inorder_index_map[root_value] - 1) root.right = array_to_tree(inorder_index_map[root_value] + 1, right) return root preorder_index = 0 # build a hashmap to store value -> its index relations inorder_index_map = {} for index, value in enumerate(inorder): inorder_index_map[value] = index return array_to_tree(0, len(preorder) - 1)
Problem
My question is about running this test case:
preorder = [4,1,3,6,8]
inorder = [6,1,8,4,3]
tree = Solution().buildTree(preorder, inorder)
When running it, an exception occurs:
Traceback (most recent call last):
File "main.py", line 43, in <module>
tree = Solution().buildTree(preorder,inorder)
File "main.py", line 30, in buildTree
return array_to_tree(0, len(preorder) - 1)
File "main.py", line 22, in array_to_tree
root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
File "main.py", line 22, in array_to_tree
root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
File "main.py", line 22, in array_to_tree
root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
File "main.py", line 23, in array_to_tree
root.right = array_to_tree(inorder_index_map[root_value] + 1, right)
File "main.py", line 22, in array_to_tree
root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
File "main.py", line 19, in array_to_tree
root_value = preorder[preorder_index]
IndexError: list index out of range
Analysis
The following is my manual calculation:
The tree should look like this:
4
/ \
1 3
/ \
6 8
Hand Calculating:
preorder = [4, 1, 3, 6, 8]
hashmap: {6:0 ; 1:1 ; 8:2 ; 4:3 ; 3:4 }
preorderindex = 0
loop 1:
left = 0 right = 3
preorderindex = 0 => root value = 4 => new right = 2
tree:
4
loop 2:
left = 0 right = 2
preorderindex = 1 => root value = 1 => new right = 0
tree:
4
/
1
loop 3:
left =0 right = 0
preorderindex = 2 => root value = 3 => new right = 3
tree:
4
/
1
/
3
At this step, there is already an error, and I really wonder where is the mistake?
I'm so confused, I don't believe there is a mistake in this code, but then I can't figure out where is my mistake?