https://programmers.co.kr/learn/courses/30/lessons/42892#qn

1. 코드

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)


def solution(nodeinfo):
    class Node:
        def __init__(self, key, value, left: None, right: None):
            self.key = key
            self.value = value
            self.left = left
            self.right = right

    class BinaryTree:
        def __init__(self):
            self.root = None

        def add(self, key, value):
            def add_node(node, key, value):
                if key < node.key:
                    if node.left is None:
                        node.left = Node(key, value, None, None)
                    else:
                        add_node(node.left, key, value)
                else:
                    if node.right is None:
                        node.right = Node(key, value, None, None)
                    else:
                        add_node(node.right, key, value)
                return True

            if self.root is None:
                self.root = Node(key, value, None, None)
                return True
            else:
                return add_node(self.root, key, value)

        # 전위순회
        def preorder(self):
            def print_subtree(node):
                if node is not None:
                    temp[0].append((node.key, node.value))
                    print_subtree(node.left)
                    print_subtree(node.right)
            print_subtree(self.root)

        # 후위순회
        def postorder(self):
            def print_subtree(node):
                if node is not None:
                    print_subtree(node.left)
                    print_subtree(node.right)
                    temp[1].append((node.key, node.value))
            print_subtree(self.root)


    answer = [[], []]
    temp = [[], []]
    mapping = defaultdict()
    for num, value in enumerate(nodeinfo):
        mapping[str(value[0]) + str(value[1])] = num + 1

    b = BinaryTree()
    nodeinfo = sorted(nodeinfo, key=lambda x: (-x[1], x[0]))
    for x, y in nodeinfo:
        b.add(x, y)
    b.preorder()
    b.postorder()

    for u, v in temp[0]:
        answer[0].append(mapping[str(u) + str(v)])
    for u, v in temp[1]:
        answer[1].append(mapping[str(u) + str(v)])
    return answer