길 찾기 게임

https://programmers.co.kr/learn/courses/30/lessons/42892
이진트리를 구성하는 노드의 x,y 좌표가 주어질 때 이진트리를 구성한 후 preorder, postorder를 리턴하는 문제

def solution(nodeinfo):
	# call stack이 100만을 넘어가는 경우가 문제에 존재하여 runtime error 발생 해결
    import sys
    sys.setrecursionlimit(10**6)
	
    #예외처리    
    if len(nodeinfo) == 1:
        return [[1], [1]]

    class BTree:
        def __init__(self, x, y, idx):
            self.x = x
            self.y = y
            self.idx = idx
            self.left = None
            self.right = None

	# 주어진 x, y좌표를 트리의 노드로 생성
    nodes = []
    for idx, (x, y) in enumerate(nodeinfo):
        node = BTree(x, y, idx+1)
        nodes.append(node)
    #노드들을 정렬하는데 트리의 높이, 트리의 x좌표를 기준으로 정렬
    nodes.sort(key = lambda elem: (elem.y, -elem.x))
    
    # 트리를 같은 level 에 속하는 node끼리 묶어줌
    node = nodes.pop()
    tree = [[node]]
    cache = node.y
    level = 0
    while nodes:
        node = nodes.pop()
        if not node.y == cache:
            level +=1
            cache = node.y
            tree.append([node])
        else:
            tree[level].append(node)

	# tree의 node들을 서로 연결. level 회수만큼 root에서 타고 내려가는데, x좌표를 기준으로 left rigt판별
    for level in range(1, len(tree)):
        for node in tree[level]:
            root = tree[0][0]
            for i in range(level-1):
                if node.x < root.x :
                    root = root.left
                else:
                    root = root.right
            if node.x < root.x:
                root.left = node
            else:
                root.right = node

	# 서치
    pre_answer = []
    post_answer = []
    def preorder(node):
        pre_answer.append(node.idx)
        if node.left:
            preorder(node.left)
        if node.right:
            preorder(node.right)
    def postorder(node):
        if node.left:
            postorder(node.left)
        if node.right:
            postorder(node.right)
        post_answer.append(node.idx)

    preorder(tree[0][0])
    postorder(tree[0][0])
    return [pre_answer, post_answer]