-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2263.py
More file actions
33 lines (23 loc) ยท 819 Bytes
/
2263.py
File metadata and controls
33 lines (23 loc) ยท 819 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
inorder_idx = {val : idx for idx, val in enumerate(inorder)}
preorder = []
def preorder_find(in_start, in_end, post_start, post_end):
if in_start > in_end or post_start > post_end :
return
root = postorder[post_end]
preorder.append(root)
root_idx_inorder = inorder_idx[root]
left_subtree_size = root_idx_inorder - in_start
preorder_find (in_start, root_idx_inorder-1, post_start, post_start + left_subtree_size - 1)
preorder_find(
root_idx_inorder + 1,
in_end,
post_start + left_subtree_size,
post_end - 1 )
preorder_find(0, N-1, 0, N-1)
print(*preorder)