프로그래머스 이진트리 문제

접근 방식(알고리즘 분류)

• 이진트리

내 풀이

#전위 순회
def pre(root, tree, now):
    global pre_result
    pre_result.append(now)
    if tree[root][0][0] != 0:
        pre(tree[root][0][0], tree, tree[root][0][1])
    if tree[root][1][0] != 0:
        pre(tree[root][1][0], tree, tree[root][1][1])

#후위 순회
def post(root, tree, now):
    global post_result
    if tree[root][0][0] != 0:
        post(tree[root][0][0], tree, tree[root][0][1])
    if tree[root][1][0] != 0:
        post(tree[root][1][0], tree, tree[root][1][1])
    post_result.append(now)

def solution(nodeinfo):
    node = []
    for i in range(len(nodeinfo)):
        node.append((nodeinfo[i][1], nodeinfo[i][0], i+1))

    # 높이를 기준으로 정렬    
    node.sort()
    print(node)

    #각 노드마다 왼쪽, 오른쪽으로 자식노드를 받을 배열 --> (노드번호, 직선거리)
    tree = [[(0,0),(0,0)] for _ in range(14)]
    root_height, root_pos, root = node.pop()
    while node:
        height, pos, now = node.pop()

        check = root_pos
        while check != 0:
            #부모보다 현재 직선거리가 더 클때
            if check < pos:
                #부모의 오른쪽 노드로 설정
                temp = tree[check][1][0]
                #부모의 오른쪽 노드가 비어있다면
                if temp == 0:
                    #오른쪽 노드로 연결
                    tree[check][1] = (pos, now)
                    break
                #비어있지 않다면 그값을 부모로 설정하고 재검사
                check = temp
            #부모보다 현재 직선거리가 더 작을 때
            else:
                temp = tree[check][0][0]
                if temp == 0:
                    tree[check][0] = (pos, value)
                    break
                check = temp

    global pre_result
    global post_result
    pre_result = []
    post_result = []
    pre(root_pos,tree,root)
    post(root_pos,tree,root)

    return [pre_result,post_result]


solution([[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]])

풀이 설명

• 매번 검색할 때마다 root노드 부터 타고타고 내려가는 방식으로 트리가 짜여진다.
• 처음에 tree를 초기화할때 설정하는 값을 잘 봐둬야 한다 --> [왼쪽노드, 오른쪽노드] --> [노드번호, 직선거리]
• 내가 가장 헷갈렸던 부분은 pos 와 now 였다. 이 둘만 정확히 체크하면서 값을 설정하면 잘 구현할 수 있었을 것 같다.