75 lines
2.4 KiB
Python
75 lines
2.4 KiB
Python
def solution(nodeinfo):
|
|
coords = {}
|
|
levels = {}
|
|
ids = {}
|
|
for id, [x, y] in enumerate(nodeinfo):
|
|
if y not in levels:
|
|
levels[y] = []
|
|
levels[y] += [x]
|
|
ids[(x, y)] = id+1
|
|
coords[id+1] = (x, y)
|
|
for y in levels:
|
|
levels[y] = sorted(levels[y])
|
|
# print(levels)
|
|
# print(ids)
|
|
|
|
root_y = max(levels.keys())
|
|
root_x = levels[root_y][0]
|
|
root_id = ids[(root_x, root_y)]
|
|
tree = {root_id: [None, None, None]} # left, right, head
|
|
windows = {(-1, root_x): -root_id, (root_x, 100001): +root_id} # -: left range, +: right range
|
|
for node_y in sorted(levels.keys(), reverse=True):
|
|
next_windows = {}
|
|
if node_y == root_y:
|
|
continue
|
|
for node_x in levels[node_y]:
|
|
node_id = ids[(node_x, node_y)]
|
|
for left, right in windows:
|
|
if left < node_x and node_x < right:
|
|
parent_id = windows[(left, right)]
|
|
is_left = parent_id < 0
|
|
parent_id = abs(parent_id)
|
|
if is_left:
|
|
tree[parent_id][0] = node_id
|
|
next_windows[(left, node_x)] = -node_id
|
|
next_windows[(node_x, coords[parent_id][0])] = +node_id
|
|
else:
|
|
tree[parent_id][1] = node_id
|
|
next_windows[(coords[parent_id][0], node_x)] = -node_id
|
|
next_windows[(node_x, right)] = +node_id
|
|
tree[node_id] =[None, None, parent_id]
|
|
windows = next_windows
|
|
# print()
|
|
# print('tree', tree)
|
|
# print()
|
|
|
|
preorder = []
|
|
queue = [root_id]
|
|
while len(queue) > 0:
|
|
node = queue.pop(0)
|
|
if node is None:
|
|
continue
|
|
preorder += [node]
|
|
left, right, parent = tree[node]
|
|
queue = [left, right, *queue]
|
|
|
|
postorder = [0]
|
|
stack = [root_id]
|
|
while len(stack) > 0:
|
|
node = stack[-1]
|
|
left, right, parent = tree[node]
|
|
if postorder[-1] == left or postorder[-1] == right:
|
|
postorder += [node]
|
|
stack.pop()
|
|
continue
|
|
if left is None and right is None:
|
|
stack.pop()
|
|
postorder += [node]
|
|
continue
|
|
if right is not None:
|
|
stack += [right]
|
|
if left is not None:
|
|
stack += [left]
|
|
|
|
return [preorder, postorder[1:]]
|