Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Reconstruction of a Tree

  Write a program which reads two sequences of nodes obtained by the preorder tree walk and the inorder tree walk on a binary tree respectively, and prints a sequence of the nodes obtained by the postorder tree walk on the binary tree.

Input

  In the first line, an integer $n$, which is the number of nodes in the binary tree, is given.

  In the second line, the sequence of node IDs obtained by the preorder tree walk is given separated by space characters.

    In the second line, the sequence of node IDs obtained by the inorder tree walk is given separated by space characters.

  Every node has a unique ID from $1$ to $n$. Note that the root does not always correspond to $1$.

Output

Print the sequence of node IDs obtained by the postorder tree walk in a line. Put a single space character between adjacent IDs.

Constraints

$1 \leq n \leq 40$

Sample Input 1

5
1 2 3 4 5
3 2 4 1 5

Sample Output 1

3 4 2 5 1

Sample Input 2

4
1 2 3 4
1 2 3 4

Sample Output 2

4 3 2 1



Sample input:
5
1 2 3 4 5
3 2 4 1 5


Sample output:
3 4 2 5 1

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.left = None
        self.right = None
        self.depth = 0
    
    def get_depth(self):
        if not self.parent:
            return 0
        else:
            return self.parent.get_depth()+1
    
    def get_sibling(self):
        if not self.parent:
            return - 1
        else:
            if self.parent.right and self.parent.right.val == self.val:
                if self.parent.left:
                    return self.parent.left.val
                else:
                    return - 1
            elif self.parent.left and self.parent.left.val == self.val:
                if self.parent.right:
                    return self.parent.right.val
                else:
                    return - 1
    
    def get_parent(self):
        if not self.parent:
            return -1
        return self.parent.val
    
    def get_degree(self):
        degree = 0
        if self.left:
            degree += 1
        if self.right:
            degree += 1
        return degree
    
    def get_type(self):
        if not self.parent:
            return "root"
        elif self.left or self.right:
            return "internal node"
        else:
            return "leaf"
    
    def get_height(self):
        if not self.left and not self.right:
            return 0
        l,r = 0,0
        if self.left:
            l = self.left.get_height()
        if self.right:
            r = self.right.get_height()
        return max(l + 1, r + 1)

def main():
    n = int(input().strip())
    nodes = [Node(i) for i in range(n)]

    ## get order
    preorder = [int(i)-1 for i in input().strip().split()] ## convert to 0-based index
    inorder = [int(i)-1 for i in input().strip().split()] ## convert to 0-based index

    def make_tree(preorder, inorder):
        if not preorder or not inorder:
            return None

        ## get root of tree
        root = nodes[preorder[0]]
        ## find divide point in inorder table
        idx = inorder.index(root.val)

        left_inorder = inorder[:idx]
        left_preorder = preorder[1:len(left_inorder)+1]
        right_inorder = inorder[idx + 1:]
        right_preorder = preorder[len(left_inorder) + 1:]

        ## create left and right tree
        root.left = make_tree(left_preorder,left_inorder)
        root.right = make_tree(right_preorder,right_inorder)

        return root

    make_tree(preorder, inorder)
    
    postorder = []

    def postorder_walk(node):
        if node.left:
            postorder_walk(node.left)
        if node.right:
            postorder_walk(node.right)
        postorder.append(str(node.val+1)) ## fix to 1-based index
    root = nodes[preorder[0]]
    postorder_walk(root)
    print(" ".join(postorder))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input().rstrip())
pre_map = input().rstrip().split(" ")
pre_map = map(int, pre_map)
in_list = input().rstrip().split(" ")
in_list = list(map(int, in_list))

result = []

def reconst(left, right):
    if left >= right:
        return 0
    c_of_pre = next(pre_map)
    c_of_in = in_list.index(c_of_pre)
    reconst(left, c_of_in)
    reconst(c_of_in+1, right)
    result.append(str(c_of_pre))
    
reconst(0, n)
print(" ".join(result))

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())  # 節点数
_Pre = [int(x) for x in sys.stdin.readline().rstrip().split()]
_In = [int(x) for x in sys.stdin.readline().rstrip().split()]


def narabekae(pre_lists, in_lists):

    # 入ってきた順列から、（根／）左側／右側を作る
    rt = pre_lists[0]

    # print(rt, pre_lists, in_lists)

    rt_idx = in_lists.index(rt)

    left = pl_lf = pre_lists[1:rt_idx + 1]
    il_lf = in_lists[:rt_idx]
    right = pl_rg = pre_lists[rt_idx + 1:]
    il_rg = in_lists[rt_idx + 1:]

    if len(left) > 1:
        left = narabekae(pl_lf, il_lf)

    if len(right) > 1:
        right = narabekae(pl_rg, il_rg)

    new_list = []
    new_list.extend(left)
    new_list.extend(right)
    new_list.extend([rt])

    # print(rt, left, right)

    return new_list


def main():

    lst = narabekae(_Pre, _In)

    print(*lst)


main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, no):
        self.no = no
        self.parent = -1
        self.left = self.right = -1
    def postorder(self):
        global t
        L = []
        if self.left >= 0: L += t[self.left].postorder()
        if self.right >= 0: L += t[self.right].postorder()
        L.append(self.no)
        return L

def makeTree(parent, preList, inList):
    global t
    if preList == []:
        return -1
    root = preList[0]
    t[root].parent = parent
    index = inList.index(root)
    t[root].left = makeTree(root, preList[1:index+1], inList[:index])
    t[root].right = makeTree(root, preList[index+1:], inList[index+1:])
    return root

n = int(input())
t = [ Node(i) for i in range(n+1) ]
preList = list(map(int, input().split()))
inList = list(map(int, input().split()))
root = makeTree(-1, preList, inList)
print(*t[root].postorder())

Submission status: Accepted

Solution code:
n = int(input())
preorder = list(map(int, input().split()))
inorder   = list(map(int, input().split()))

root_used = []

def find(c, branch):
    for i, x in enumerate(branch):
        if x==c:
            return i
    return None
    
i = 0
ans = []
    
def reconstruction(branch):
    global i
    
    if len(branch)==0:
        return
        
    if i>=len(preorder):
        return
    
    c = preorder[i]
    i += 1
    m = find(c, branch)
    
    if m is None:
        return 
    
    left_branch = branch[:m]
    right_branch = branch[m+1:]
    
    reconstruction(left_branch)
    reconstruction(right_branch)
    
    ans.append(c)
    
reconstruction(inorder)

print(*ans)

Submission status: Accepted

Solution code:
N = int(input())

pre_list = list(map(lambda s: int(s) - 1, input().split()))
in_list = list(map(lambda s: int(s) - 1, input().split()))
post_list = []


def f(n, left, right):
    num = pre_list[n]

    if right - left == 1:
        post_list.append(num)
        return
        
    idx = in_list.index(num)
    n += 1
    if idx - left >= 1:
        f(n, left, idx)
    n += idx - left
    if right - idx - 1 >= 1:
        f(n, idx+1, right)
    post_list.append(num)


f(0, 0, N)
print(' '.join(map(lambda x: str(x+1), post_list)))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
preorder=(x for x in A)
postorder=[]

def recontruction(l,r):
    if l>=r:
        return None
    c=next(preorder)
    m=B.index(c)
    recontruction(l,m)
    recontruction(m+1,r)
    postorder.append(c)
    

recontruction(0,n)
print(*postorder)

Submission status: Accepted

Solution code:
n = int(input())
P = list(map(int,input().split()))
I = list(map(int,input().split()))

post = 0
ans = []
def reconstruction(l,r):
    global post
    if l >= r:
        return None
    c = P[post]
    post += 1
    for i in range(n):
        if c == I[i]:
            reconstruction(l,i)
            reconstruction(i+1,r)
    ans.append(c)

reconstruction(0,n)

for i,a in enumerate(ans):
    if i != n-1:
        print(a,end=" ")
    else:
        print(a)

Submission status: Accepted

Solution code:
n = int(input())
pre = list(map(int,input().split()))
ino = list(map(int,input().split()))
pos = []

def reconstruction(l, r):
    if l >= r :
        return
    c = pre.pop(0)
    m = ino.index(c)
#     print("c", c, l, r, m)
    reconstruction(l, m)
    reconstruction(m+1, r)
    
    global pos
    pos += [c]

reconstruction(0, len(ino))
print(" ".join([str(ss) for ss in pos]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

N = int(input())
left = list(map(int,input().split()))
middle = list(map(int,input().split()))

ans = []
def dfs(p,end,L,R):
    #print("p: {},end: {},L: {},R: {}".format(p,end,L,R))
    if end == p + 1:
        ans.append(left[p])
        return
    for i in range(L,R):
        if middle[i] == left[p]:
            idx = i
            break
    if idx != L:
        dfs(p + 1,p + idx - L + 1,L,idx)
    if idx != R - 1:
        dfs(p + idx - L + 1,end,idx + 1,R)
    ans.append(left[p])
dfs(0,N,0,N)
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
n = int(input())
PRE = list(map(int,input().split()))
IN =  list(map(int,input().split()))
post =[]
pos = 0

def rec(l,r):
    global pos
    if l >= r : return
    root = PRE[pos]
    pos += 1
    m = IN.index(root)
    rec(l,m)
    rec(m+1,r)
    post.append(root)

def solve():
    rec(0,len(PRE))
    for i in range(n):
        if i == n-1:
            print(post[i])
        else:
            print(post[i],"",end = "")

solve()

Submission status: Accepted

Solution code:
def toPostorder(prelist, inlist):
    parent = prelist[0]
    split_index = inlist.index(parent)
    if split_index != 0:
        yield from toPostorder(prelist[1:split_index + 1],inlist[0:split_index])
    if split_index != len(inlist)-1:
        yield from toPostorder(prelist[split_index + 1:],inlist[split_index + 1:])

    yield parent

nodes = dict()
n = int(input())
preorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))
print(*toPostorder(preorder, inorder))

Submission status: Accepted

Solution code:
n = int(input())
preorder = list(map(int,input().split()))
inorder = list(map(int,input().split()))
postorder = []

def rec(l):
    if len(l) == 0:
        return
    # preorderから次の値を取り出す
    x = preorder.pop(0)
    for i in range(len(l)):
        if l[i] == x:
            # preorderの値と一致したら、そこから左右に分割
            rec(l[:i])
            rec(l[i+1:])
    postorder.append(x)
    return

rec(inorder)
print(*postorder)

Submission status: Accepted

Solution code:
N=int(input())
preorder=list(map(int,input().split()))
inorder=list(map(int,input().split()))
pre_iter=iter(preorder)
bisect_tree = [[None,None] for i in range(N+1)]

def reconst(l,r):
    global pre_iter
    if r-l <= 0:
        return
    if r-l == 1:
        next(pre_iter)
        return inorder[l]
    partial_root = next(pre_iter)
    partial_root_position = inorder.index(partial_root)
    left_child = reconst(l,partial_root_position)
    right_child = reconst(partial_root_position+1,r)
    bisect_tree[partial_root][0]=left_child
    bisect_tree[partial_root][1]=right_child
    return partial_root
ans=[]
def postorder(node):
    if bisect_tree[node] == [None,None]:
        ans.append(node)
    else:
        if bisect_tree[node][0] != None:
            postorder(bisect_tree[node][0])
        if bisect_tree[node][1] != None:
            postorder(bisect_tree[node][1])
        ans.append(node)

def root_search():
    parent=[-1]*(N+1)
    for i in range(1,N+1):
        if bisect_tree[i][0] != None:
            parent[bisect_tree[i][0]]=i
        if bisect_tree[i][1] != None:
            parent[bisect_tree[i][1]]=i
    for i in range(1,N+1):
        if parent[i] == -1:
            break
    return i

reconst(0,N)
root = root_search()
postorder(root)
print(*ans)

Submission status: Accepted

Solution code:
def search(l):
    global i
    if len(l) == 0:
        return
    v = p[i]
    i += 1
    for j in range(len(l)):
            if l[j] == v:
                id = j
                break
    if len(l) != 1:
        search(l[:id])
        search(l[id+1:])
        ans.append(v)
    else:
        ans.append(v)

n = int(input())
p = [int(_) for _ in input().split()]
m = [int(_) for _ in input().split()]
i = 0
ans = []
search(m)
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
n = int(input())
Pre = list(map(int, input().split()))
In = list(map(int, input().split()))

def gao(Pre, l, r, In: list, L, R):
    if l > r:
        return []
    offset = In.index(Pre[l]) - L
    return gao(Pre, l + 1, l  + offset, In, L, L + offset - 1) + gao(Pre, l + offset + 1, r, In, L + offset + 1, R) + [Pre[l]]

print(*gao(Pre, 0, n - 1, In, 0, n - 1))

Submission status: Accepted

Solution code:
N = int(input())
PRE = [int(i) for i in input().split()]
IN = [int(i) for i in input().split()]
POST = []

pos = 0

def rec(left, right):
    global pos
    if right <= left:
        return
    root = PRE[pos]
    pos += 1
    mid = IN.index(root)
    rec(left, mid)
    rec(mid + 1, right)
    POST.append(root)

rec(0, N)
print(*POST)

Submission status: Accepted

Solution code:
from collections import deque
postorder = list()

def reconstruction(preorder, inorder, l, r):
    if l >= r:
        return

    c = preorder.popleft()
    m = inorder.index(c)
    reconstruction(preorder, inorder, l, m)
    reconstruction(preorder, inorder, m + 1, r)
    postorder.append(str(c))

def Main():
    N = int(input())
    preorder = deque(map(int, input().split()))
    inorder = deque(map(int, input().split()))
    reconstruction(preorder, inorder, 0, N)
    print(*postorder)

Main()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,parent=-1,left=-1,right=-1):
        self.parent = parent
        self.left = left
        self.right = right
    
def postorder(ns,i,post):
    if ns[i].left != -1:
        postorder(ns,ns[i].left,post)
    if ns[i].right != -1:
        postorder(ns,ns[i].right,post)
    post.append(str(i+1))

def poio_node(ns,po,io):
    p = po[0]
    i = io.index(p)
    if i != 0:
        ns[p].left = po[1]
        ns[po[1]].parent = p
        poio_node(ns,po[1:i+1],io[:i])
    if i != len(io)-1:
        ns[p].right = po[i+1]
        ns[po[i+1]].parent = p
        poio_node(ns,po[i+1:],io[i+1:])

def min1(n):
    return n-1

n = int(input())
po = list(map(int,input().split()))
io = list(map(int,input().split()))
po = list(map(min1,po))
io = list(map(min1,io))
ns =[Node() for _ in range(n)]

poio_node(ns,po,io)
post=[]
postorder(ns,po[0],post)
print(" ".join(post))

Submission status: Accepted

Solution code:
# Tree Walk


N = int(input())
*A, = map(int, input().split())
*B, = map(int, input().split())
idx = 0
ans = []


def rec(l=0, r=N):
    global idx
    if l >= r:
        return

    c = A[idx]
    idx += 1
    m = B.index(c)

    rec(l, m)
    rec(m+1, r)

    ans.append(c)


rec()
print(*ans)

Submission status: Accepted

Solution code:
postorder = []

def printpostorder(inorder, preorder, n): 
    if preorder[0] in inorder: 
        root = inorder.index(preorder[0]) 
          
    if root != 0: # left subtree exists 
        printpostorder(inorder[:root],  
                       preorder[1:root + 1],  
                       len(inorder[:root])) 
      
    if root != n - 1: # right subtree exists 
        printpostorder(inorder[root + 1:],   
                       preorder[root + 1:],  
                       len(inorder[root + 1:])) 
    
    postorder.append(preorder[0])
          

n = int(input())
preorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))
printpostorder(inorder, preorder, n)

print( " ".join( [ str(i) for i in postorder ]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.left = -1
        self.right = -1
        
N = int(input())
nodes = [Node(i+1) for i in range(N)]

preorders = [int(i)-1 for i in input().split()]
inorders = [int(i)-1 for i in input().split()]


def dfs(nodes, preo, ino):
    if not preo:
        return

    root = preo[0]
    i = ino.index(root)
    
    if i != 0:
        nodes[root].left = preo[1]
        nodes[preo[1]].parent = root
        dfs(nodes, preo[1:i+1], ino[:i])
    
    if i != len(ino)-1:
        nodes[root].right = preo[i+1]
        nodes[preo[i+1]].parent = root
        dfs(nodes, preo[i+1:], ino[i+1:])
    

def postorder(nodes, root, result):
    node = nodes[root]
    if node.left != -1:
        postorder(nodes, node.left, result)
    if node.right != -1:
        postorder(nodes, node.right, result)
    result.append(root+1)


dfs(nodes, preorders, inorders)

result = []
postorder(nodes, preorders[0], result)

print(*result)

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write= sys.stdout.write

N = int(readline())
s0 = map(int, readline().split())
s1 = map(int, readline().split())
st0 = []; st1 = []
que = deque()
q = next(s1, None)
j = -1
ans = []
for v in s0:
    while st1 and st1[-1] != j:
        ans.append(st1.pop())
    st1.append(v)

    st0.append(v)
    j = v
    while st0 and st0[-1] == q:
        j = st0.pop()
        q = next(s1, None)
while st1:
    ans.append(st1.pop())
print(*ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    pre = list(map(int, input().split()))
    in_ = list(map(int, input().split())) # pythonではinは予約語
    post = []

    pos = 0

    def rec(l, r,):
        global pos # posはglobal変数だと明示する
        if l >= r:
            return
        root = pre[pos]
        pos += 1
        m = in_.index(root)
        rec(l, m)
        rec(m+1, r)
        post.append(str(root))

    rec(0, n)
    print(' '.join(post))

Submission status: Accepted

Solution code:
def set_children(inorder_list):
    global p
    rn = preorder[p]
    i = inorder_list.index(rn)
    left_side = inorder_list[:i]
    right_side = inorder_list[i:]
    right_side.remove(rn)
    if left_side:
        p += 1
        set_children(left_side)
    if right_side:
        p += 1
        set_children(right_side)
    postorder.append(rn)

if __name__ == "__main__":
    p = 0
    n = int(input())
    preorder = input().split()
    inorder = input().split()
    postorder = []
    set_children(inorder[:])
    print(" ".join(postorder))

Submission status: Accepted

Solution code:
# Reconstruction of the Tree

# Tree walk

import sys
sys.setrecursionlimit(10**9)  # 再帰回数上限の向上 かなり多くしないとREになる


def rec(l, r, post_ls):
    if (l >= r):
        return
    global pos
    root = pre_ls[pos]
    pos +=1
    m = in_ls.index(root)
    rec(l, m, post_ls)
    rec(m + 1, r, post_ls)
    post_ls.append(root)

# データの読み込み
n = int(input())
pre_ls = list(map(int, input().split()))
in_ls = list(map(int, input().split()))
post_ls = []

pos = 0
rec(0, len(pre_ls), post_ls)

print(*post_ls)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, id):
        self.id = id
        self.left = -1
        self.right = -1
def walk_postorder(node, order_list):
    if node == None:
        return 0
    walk_postorder(nodes.get(node.left), order_list)
    walk_postorder(nodes.get(node.right), order_list)
    order_list.append(node.id)
def build_tree(nodes, preorder, inorder, start_idx, end_idx):
    node = Node(preorder[build_tree.pre_idx])
    nodes[preorder[build_tree.pre_idx]] = node
    build_tree.pre_idx += 1
    
    if start_idx == end_idx:
        return node
    
    root_idx = inorder.index(node.id)
    if start_idx != root_idx:
        left = build_tree(nodes, preorder, inorder, start_idx, root_idx-1)
        nodes[node.id].left = left.id
    if end_idx != root_idx:
        right = build_tree(nodes, preorder, inorder, root_idx+1, end_idx)
        nodes[node.id].right = right.id
    
    return node

n = int(input())
preorder = list(map(int, input().split(' ')))
inorder = list(map(int, input().split(' ')))
nodes = {}
build_tree.pre_idx = 0
build_tree(nodes, preorder, inorder, 0, n-1)
postorder_list = []
walk_postorder(nodes[preorder[0]], postorder_list)
print(' '.join(map(str, postorder_list)))

Submission status: Accepted

Solution code:
n = int(input())

Pr = list(map(int, input().split()))
I = list(map(int, input().split()))
Po = []

def Rec(Pr,I):
  a = I.index(Pr[0])
  if a >= 1:
    Rec(Pr[1:a+1],I[0:a])
    if a < len(Pr)-1:
      Rec(Pr[a+1:],I[a+1:])
    Po.append(Pr[0])
  else:
    A = []
    A.append(Pr[0])
    if len(Pr) > 1:
      Rec(Pr[1:],I[1:])
    while A != []:
      Po.append(A.pop())

Rec(Pr, I)

print(" ".join(map(str, Po)))

Submission status: Accepted

Solution code:
import sys

def postordered_tree_walk(preordered, inordered, route):
    def work(pos, l_in, r_in):
        if (l_in >= r_in): return

        root_id = preordered[pos]
        split_point = inordered.index(root_id, l_in, r_in)

        work(pos + 1, l_in, split_point)
        work(pos + (split_point - l_in) + 1, split_point + 1, r_in)
        route.append(root_id)

    work(0, 0, len(inordered))

n = int(input())
preordered_route = list(map(int, sys.stdin.readline().split()))
inordered_route = list(map(int, sys.stdin.readline().split()))

postordered = []
postordered_tree_walk(preordered_route, inordered_route, postordered)

print(*postordered)

Submission status: Accepted

Solution code:
def reconstruction(left, right, pre_order, in_order, traversal):
    if left >= right:
        return traversal
    else:
        next_pre_node = pre_order.pop(0)
        pos_in_order = in_order.index(next_pre_node)

        traversal = reconstruction(left, pos_in_order, pre_order, in_order, traversal)
        traversal = reconstruction(pos_in_order + 1, right, pre_order, in_order, traversal)
        traversal.append(next_pre_node)
        return traversal


if __name__ == "__main__":
    n = int(input())
    pre_order = list(map(int, input().split()))
    in_order = list(map(int, input().split()))
    traversal = reconstruction(0, n, pre_order, in_order, [])
    print(*traversal)

Submission status: Accepted

Solution code:
class BinaryNode():
    def __init__(self, parent=-1, left=-1, right=-1, depth=-1, height=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.height = height


class BinaryTree(list):
    def __init__(self, obj):
        if isinstance(obj, int):
            super().__init__([BinaryNode() for _ in range(obj)])
            self.len = obj
        elif isinstance(obj, list):
            super().__init__(obj)
            self.len = len(obj)
        else:
            raise TypeError("arg should be int or list of binarynodes")
        self.root = None

    # def __getitem__(self, idxs):
    #     if isinstance(idxs, tuple):
    #         return BinaryTree(list(self)[idxs])
    #     return super().__getitem__(idxs)

    def set_node(self, id, left, right):
        self[id].left = left
        self[id].right = right
        if left > -1:
            self[left].parent = id
        if right > -1:
            self[right].parent = id

    def __set_depth(self, id, depth):
        self[id].depth = depth
        if self[id].left > -1:
            self.__set_depth(self[id].left, depth + 1)
        if self[id].right > -1:
            self.__set_depth(self[id].right, depth + 1)

    def set_depth(self):
        self.__set_depth(self.root, 0)

    def __set_height(self, id):
        if id == -1:
            return -1
        height = 1 + max(self.__set_height(self[id].left), self.__set_height(self[id].right))
        self[id].height = height
        return height

    def set_height(self):
        self.__set_height(self.root)

    def set_root(self):
        for i in range(self.len):
            if self[i].parent == -1:
                self.root = i
                break

    def get_nodetype(self, i):
        if self[i].parent == -1:
            return "root"
        elif self[i].left == -1 and self[i].right == -1:
            return "leaf"
        else:
            return "internal node"

    def get_sibling(self, i):
        parent = self[i].parent
        if parent == -1:
            return -1
        if self[parent].left == i:
            return self[parent].right
        else:
            return self[parent].left

    def get_degree(self, i):
        return (self[i].left > -1) * 1 + (self[i].right > -1) * 1

    def set_all(self):
        self.set_root()
        self.set_depth()
        self.set_height()

    def print(self):
        for i in range(self.len):
            print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
                i, self[i].parent, self.get_sibling(i), self.get_degree(i),
                self[i].depth, self[i].height, self.get_nodetype(i)))

    def __preorder(self, id):
        if id == -1:
            return []
        return [id] + self.__preorder(self[id].left) + self.__preorder(self[id].right)

    def order_list(self, order_type):
        if order_type == 0:
            return self.__preorder(self.root)
        elif order_type == 1:
            return self.__inorder(self.root)
        else:
            return self.__postorder(self.root)

    def order_str(self, order_type):
        return " ".join(map(str, self.order_list(order_type)))

    def __inorder(self, id):
        if id == -1:
            return []
        return self.__inorder(self[id].left) + [id] + self.__inorder(self[id].right)

    def __postorder(self, id):
        if id == -1:
            return []
        return self.__postorder(self[id].left) + self.__postorder(self[id].right) + [id]


def get_root(preorder, inorder, num, tree):
    root = preorder[0]
    if num == 1:
        return root
    root_idx = inorder.index(root)
    left_inorder = inorder[:root_idx]
    left_preorder = preorder[1:1 + root_idx]
    left_num = root_idx
    right_inorder = inorder[root_idx + 1:]
    right_preorder = preorder[1 + root_idx:]
    right_num = num - root_idx - 1
    if left_num > 0:
        left = get_root(left_preorder, left_inorder, left_num, tree)
        if left > -1:
            tree[root].left = left
            tree[left].parent = root
    if right_num > 0:
        right = get_root(right_preorder, right_inorder, right_num, tree)
        if right > -1:
            tree[root].right = right
            tree[right].parent = root
    return root


def main():
    n = int(input())
    preorder = input().split(" ")
    preorder = list(map(lambda x: int(x) - 1, preorder))
    inorder = input().split(" ")
    inorder = list(map(lambda x: int(x) - 1, inorder))
    tree = BinaryTree(n)
    tree.root = get_root(preorder, inorder, n, tree)
    print(" ".join(map(lambda x: str(x + 1), tree.order_list(2))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def reconstruction(left, right):
    global pos
    if left >= right:
        return
    c = preorder[pos]
    pos += 1
    m = inorder.index(c)
    reconstruction(left, m)
    reconstruction(m + 1, right)
    postorder.append(str(c))

pos = 0
postorder = []

n=int(input())
preorder=list(map(int,input().split()))
inorder=list(map(int,input().split()))
reconstruction(0, n)
print(' '.join(postorder))

Submission status: Accepted

Solution code:
N = int(input())
preorder = list(map(lambda s: int(s) - 1, input().split()))
inorder = list(map(lambda s: int(s) - 1, input().split()))
postorder = []


def f(n, left, right):
    num = preorder[n]
    # print(n, left, right, num)
    if right - left == 1:
        postorder.append(num)
        return
    idxin = inorder.index(num)
    n += 1
    if idxin - left >= 1:
        f(n, left, idxin)
    n += idxin - left
    if right - idxin - 1 >= 1:
        f(n, idxin+1, right)
    postorder.append(num)


f(0, 0, N)
print(' '.join(map(lambda x: str(x+1), postorder)))

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def postorder(root, out):
    if root == None:
        pass
    else:
        postorder(root.left, out)
        postorder(root.right, out)
        out.append(root.value)

def build_tree(pres, ins):
    if len(pres) < 1:
        return None
    else:
        node = Node(pres[0])
        index = 0
        for i in range(len(ins)):
            if ins[i] == pres[0]:
                index = i
                break
        
        node.left = build_tree(pres[1:1+index], ins[0:index])
        node.right = build_tree(pres[1+index:], ins[1+index:])
        return node


if __name__ == '__main__':
    n = int(input())
    pres = [int(num) for num in input().split(' ')]
    ins = [int(num) for num in input().split(' ')]
    root = build_tree(pres, ins)
    out = []
    postorder(root, out)
    print(str(out).replace(',', '').replace('[', '').replace(']', ''))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def find_chi(l, r):
        if l == r:
            return l
        min_pre_i = n + 1
        pui = -1
        for ino_i in range(l, r + 1):
            if pre_i[ino_i] < min_pre_i:
                min_pre_i = pre_i[ino_i]
                pui = ino_i
        if pui - l > 0:
            chi[ino[pui]][0] = ino[find_chi(l, pui - 1)]
        if r - pui > 0:
            chi[ino[pui]][1] = ino[find_chi(pui + 1, r)]
        return pui

    def dfs(u):
        l, r = chi[u]
        if l != -1: dfs(l)
        if r != -1: dfs(r)
        pos.append(u)

    n = int(input())
    pre = list(map(int, input().split()))
    ino = list(map(int, input().split()))
    chi = {}
    for u in pre:
        chi[u] = [-1, -1]
    utoi = {u: i for i, u in enumerate(pre)}
    pre_i = []
    for u in ino:
        pre_i.append(utoi[u])
    root = ino[find_chi(0, n - 1)]
    pos = []
    dfs(root)
    print(*pos)

main()

Submission status: Accepted

Solution code:

def reconstruction(left, right):
    if left >= right:
        return

    global position, pre, ino, post
    root = pre[position]
    position += 1

    mid = ino.index(root)  # inoでのrootのポジション
    reconstruction(left, mid)
    reconstruction(mid + 1, right)

    post.append(root)


n = int(input())

pre = list(map(int, input().split()))
ino = list(map(int, input().split()))
post = []

position = 0
reconstruction(0, n)

print(' '.join(map(str, post)))