In [13]:
1
2
from binarytree import tree, build, Node
from typing import List
105. Construct Binary Tree from Preorder and Inorder Traversal
In [18]:
1
2
3
4
5
# toy example
root = tree(height=3)
root.pprint()
print(root.preorder)
print(root.inorder)
1
2
3
4
5
6
7
8
9
10
11
12
_____10_____
/ \
___9 ___7
/ \ / \
8 14 12 6
/ \ \ \
1 13 0 4
[Node(10), Node(9), Node(8), Node(1), Node(13), Node(14), Node(0), Node(7), Node(12), Node(4), Node(6)]
[Node(1), Node(8), Node(13), Node(9), Node(14), Node(0), Node(10), Node(12), Node(4), Node(7), Node(6)]
Idea
I cited an idea from discuss
I cited a user’s comment from the leetcode.
Looking at preorder traversal, the first value (node 1) must be the root.
Then, we find the index of root within in-order traversal, and split into two sub problems
Therefore, the tree can be constructed in the preorder by referring to the given inorder.
Tip
a built-in function of
listislist.index, which find the index from the given value.
In [33]:
1
2
3
4
5
6
7
8
9
10
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Node:
if not inorder: # if inorder is empty, return
return None
idx = inorder.index(preorder.pop(0))
root = Node(inorder[idx])
root.left = self.buildTree(preorder, inorder[:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return root
sol = Solution()
In [34]:
1
2
3
4
5
6
7
8
root.pprint()
preorder = list(map(lambda x: x.value, root.preorder))
inorder = list(map(lambda x: x.value, root.inorder))
print(preorder)
print(inorder)
print("-"*50)
ans = sol.buildTree(preorder, inorder)
ans.pprint()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
_____10_____
/ \
___9 ___7
/ \ / \
8 14 12 6
/ \ \ \
1 13 0 4
[10, 9, 8, 1, 13, 14, 0, 7, 12, 4, 6]
[1, 8, 13, 9, 14, 0, 10, 12, 4, 7, 6]
--------------------------------------------------
_____10_____
/ \
___9 ___7
/ \ / \
8 14 12 6
/ \ \ \
1 13 0 4
Leave a comment