프로그래머스 LV3 - 길 찾기 게임

문제 링크

풀이 1 (재귀 사용 x)

class Node:
    def __init__(self, info, num, left = None, right = None):
        self.info = info
        self.left = left
        self.right = right
        self.num = num
    
    def has_left(self):
        return self.left is not None
    
    def has_right(self):
        return self.right is not None
    
def make_BT(nodeinfo):
    nodes = [i for i in range(1, len(nodeinfo) + 1)]
    nodes.sort(key = lambda x : (-nodeinfo[x-1][1] , nodeinfo[x-1][0]))
    root = None
    for i in range(len(nodes)):
        if root is None:
            root = Node(nodeinfo[nodes[0]-1],nodes[0])
        else:
            parent = root
            node = Node(nodeinfo[nodes[i]-1], nodes[i])
            while True:
                if node.info[0] < parent.info[0]:
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = node
                    break
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = node
                    break
    return root
        
def pre_order(root, answer):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        answer[0].append(node.num)
        stack.append(node.right)
        stack.append(node.left)
def post_order(root, answer):
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node is None:
            continue
        if visited:
            answer[1].append(node.num)
        else:
            stack.append((node,True))
            stack.append((node.right, False))
            stack.append((node.left, False))
    
    
def solution(nodeinfo):
    answer = [[], []]
    root = make_BT(nodeinfo)
    pre_order(root,answer)
    post_order(root, answer)
    return answer

풀이 2 (재귀 사용 O)

import sys
sys.setrecursionlimit(10 ** 6)

class Node:
    def __init__(self, info, num, left = None, right = None):
        self.info = info
        self.left = left
        self.right = right
        self.num = num
    
    def has_left(self):
        return self.left is not None
    
    def has_right(self):
        return self.right is not None
    
def make_BT(nodeinfo):
    nodes = [i for i in range(1, len(nodeinfo) + 1)]
    nodes.sort(key = lambda x : (-nodeinfo[x-1][1] , nodeinfo[x-1][0]))
    root = None
    for i in range(len(nodes)):
        if root is None:
            root = Node(nodeinfo[nodes[0]-1],nodes[0])
        else:
            parent = root
            node = Node(nodeinfo[nodes[i]-1], nodes[i])
            while True:
                if node.info[0] < parent.info[0]:
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = node
                    break
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = node
                    break
    return root
        
def pre_order(root, answer):
    if root is None:
        return
    answer[0].append(root.num)
    pre_order(root.left, answer)
    pre_order(root.right, answer)
    
def post_order(root, answer):
    if root is None:
        return
    post_order(root.left, answer)
    post_order(root.right, answer)
    answer[1].append(root.num)
    
def solution(nodeinfo):
    answer = [[], []]
    root = make_BT(nodeinfo)
    pre_order(root,answer)
    post_order(root, answer)
    return answer