acmicpc.net 9934(트리, BFS), 5639(이진 트리), 6597(트리)

https://www.acmicpc.net/problem/9934

풀긴했는데 그닥 만족스럽지 못한 코드다. 이렇게 하는게 맞는건지...

# -*- encoding: cp949 -*-
import Queue
def bfs(k):
    q = Queue.Queue()
    q.put([k,k/2])
    while not q.empty():
        p = q.get()
        temp = []
        flag = False
        for e in p[:-1]:
            temp.append(e-p[-1]-1)
            temp.append(e+p[-1]+1)
            if e+p[-1]-1<0 or e+p[-1]+1>len(n)-1:
                flag = True
            print n[e],
        print
        if flag: return
        temp.append(p[-1]/2)
        q.put(temp)

k=input()
n = map(int,raw_input().split())
bfs(2**(k-1)-1)

https://www.acmicpc.net/problem/5639

받은 인자들로 이진 트리를 만든다. 전위순회값을 주므로 루트는 제일 처음 값이다.

그 후에 만들어진 이진검색트리로 후위순해해서 보여주면 된다.

# -*- encoding: cp949 -*-
def post(e):
    if e=='': return
    post(d[e][0])
    post(d[e][1])
    print e

e = []
while True:
    try: e.append(input())
    except EOFError: break
d={e[0]:['','']}
for element in e[1:]:
    c = e[0]
    while True:
        if element < c:
            if d[c][0]=='':
                d[c][0] = element
                d[element] = ['','']
                break
            else:
                c = d[c][0]
        elif element > c:
            if d[c][1]=='':
                d[c][1] = element
                d[element] = ['','']
                break
            else:
                c = d[c][1]
post(e[0])

https://www.acmicpc.net/problem/6597

앞에 4256번이랑 똑같다. 프리오더와 인오더로 포스트오더를 구하는문제.

# -*- encoding: cp949 -*-
def post(_pre, _in):
    global ans
    if not _pre: return
    root = _pre[0]
    if type(_in) is int:
        _in = [_in]
    l = _in.index(root)
    r = len(_pre) - 1 - l
    post(_pre[1:l+1], _in[:l])
    post(_pre[l+1:], _in[l+1:])
    ans += str(root)
 
while True:
    try:
        _pre,_in = map(list,raw_input().split())
        ans = ''
        post(_pre, _in)
        print ans
    except EOFError: break