프로그래머스 길 찾기 게임

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

트리 순회에 관한 문제였다.

문제의 핵심은 트리를 구현하고 재귀를 통해 순회할 수 있는지 알아보는 문제였다.
트리를 구현하는데 있어서 접근방법이 떠오르지 않았다. 이진트리에 대한 이해가 부족했다고 생각한다.
x의 값에 따라 루트의 왼쪽으로 갈지 오른쪽으로 갈지 정하는 방법이었는데, x값이 루트보다 작은경우 루트보다 작은 x값을 가지는 것들을 filter를 통해 다 왼쪽으로 넣어주고 재귀를 돌렸다.

아직 재귀에 대해 이러한 설계능력이 부족한 것 같다.
왼쪽 노드들을 다 넣고 다시 재귀를 돌리고.. 이미 완성된 재귀의 형태를 보면 자명하다는 것이 확 와닫지만, 막상 실제로 구현하기가 어려운것 같다.

import sys
sys.setrecursionlimit(10**6)
def solution(nodeinfo):
    class Tree:
        def __init__(self, nodelist):
            self.root = max(nodelist, key = lambda x: x[1])
            leftnode = list(filter(lambda x: x[0] < self.root[0], nodelist))
            rightnode = list(filter(lambda x: x[0] > self.root[0], nodelist))
            
            if leftnode != []:
                self.left = Tree(leftnode)
            else:
                self.left = None
            if rightnode != []:
                self.right = Tree(rightnode)
            else:
                self.right = None
    def traversal(node, preorder, postorder):
        preorder.append(node.root)  ## Root 
        if node.left is not None:
            traversal(node.left, preorder, postorder) ## Left
        if node.right is not None:
            traversal(node.right, preorder, postorder) ## Right
        postorder.append(node.root)
            
        
    tree = Tree(nodeinfo)
    preorder = []
    postorder = []
    answer = []
    traversal(tree, preorder, postorder)
    answer.append(list(map(lambda x: nodeinfo.index(x) + 1, preorder)))
    answer.append(list(map(lambda x: nodeinfo.index(x) + 1, postorder)))
    return answer