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:


class Node:
    def __init__(self,name):
        self.name=name
        self.left=-1
        self.right=-1
        self.parent=-1



def mk_tree(Tree,p_order,in_order):
    tmp_p_order=[]
    tmp_in_order=[]
    root=p_order[0]#p_orderの先頭要素が、rootになる

    root_ind=0    
    while(in_order[root_ind] != root):
        root_ind+=1#in_orderでのrootのindexを返す 



    if(root_ind!=0):
        Tree[root].left=p_order[1]
        Tree[p_order[1]].parent=root
        tmp_in_order=in_order[0:root_ind]
        tmp_p_order=p_order[1:root_ind+1]
        mk_tree(Tree,tmp_p_order,tmp_in_order)

    if(root_ind!=len(p_order)-1):
        Tree[root].right=p_order[root_ind+1]
        Tree[p_order[root_ind+1]].parent=root
        tmp_in_order=in_order[root_ind+1:]
        tmp_p_order=p_order[root_ind+1:]
        mk_tree(Tree,tmp_p_order,tmp_in_order)
    


def Postorder(Tree,root,order):
    if(Tree[root].left!=-1):
        Postorder(Tree,Tree[root].left,order)
    if(Tree[root].right!=-1):
        Postorder(Tree,Tree[root].right,order)
    order.append(root)
       






n=int(input())
p_order=list(map(int,input().split()))
root=p_order[0]
in_order=list(map(int,input().split()))
Tree=[None]
for i in range(n):
   Tree.append(Node(i+1))

mk_tree(Tree,p_order,in_order)

#for i in range(1,n+1):
 #  print(f"id {i}: left = {Tree[i].left}, right = {Tree[i].right}, parent = {Tree[i].parent}")



post_order=[]
Postorder(Tree,root,post_order)
print(" ".join(list(map(str,post_order))))

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:
j, a = 0, []
def f(l, r):
    if l < r:
        global j, a
        c = P[j]
        j += 1
        m = I.index(c)
        f(l, m)
        f(m + 1, r)
        a += [c]


N = int(input())
P = input().split()
I = input().split()
f(0, N)
print(*a)

Submission status: Accepted

Solution code:
def post(P, I):
    if len(I)==0:
        return ""
    elif len(I)==1:
        return I[0]
    else:
        root = I.index(P[0])
        right = len(P)
        for i in I[root+1:]:
            if P.index(i) < right:
                right = P.index(i)
        return post(P[1:right],I[:root]) + " " + post(P[right:], I[root+1:]) + " " + I[root]
    
n = int(input())
P = input().split()
I = input().split()
ans = ""
for i in post(P,I).split():
    ans+=i + " "
print(ans[:-1])

Submission status: Accepted

Solution code:
pos = 0

def reconstruction(pre_order, in_order, post_order, left, right):
    if left >= right:
        return
    global pos
    root = pre_order[pos]
    pos += 1
    mid = in_order.index(root)
    reconstruction(pre_order, in_order, post_order, left, mid)
    reconstruction(pre_order, in_order, post_order, mid + 1, right)
    post_order.append(root)


def solve(pre_order, in_order):
    post_order = []
    reconstruction(pre_order, in_order, post_order, 0, len(pre_order))
    print(' '.join([str(v) for v in post_order]))


n = int(input())
pre_order = [int(v) for v in input().split()]
in_order = [int(v) for v in input().split()]

solve(pre_order, in_order)

Submission status: Accepted

Solution code:
# Tree - Reconstruction of a Tree
class Node:
    none = 0
    right = 1
    left = -1
    def is_leaf(self):
        d = 1 if self.right else 0
        d += 1 if self.left else 0
        return self.depth > 0 and d == 0
    def num_child(self):
        d = 1 if self.right else 0
        d += 1 if self.left else 0
        return d
    
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.sibling = None
        # ?????¨?????¨????????¨?????¨????????¨
        self.right,self.left = None,None
        self.depth = 0
        self.height = 0
        self.position = Node.none
    def __str__(self):
        p = self.parent.id if self.parent else -1
        s = self.sibling.id if self.sibling else -1
        d = 1 if self.right else 0
        d += 1 if self.left else 0
        typ = 'root'
        if self.depth > 0: typ = 'internal node'
        if d == 0 and self.depth > 0: typ = 'leaf'
        h = self.height
        return 'node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(self.id, p, s, d, self.depth, h, typ)

def calc_cld_depth(nd):
    """?????????????????±???????¨??????????"""
    if nd.left:
        nd.left.depth = nd.depth + 1
        calc_cld_depth(nd.left)
    if nd.right:
        nd.right.depth = nd.depth + 1
        calc_cld_depth(nd.right)

def rec(preo, ino):
    idx = -1
    proot = None # ??¨?????¨????????????
    for p in preo:
        if p in ino:
            idx = ino.index(p)
            proot = p
            break
    else:
        raise # unexpected error
    # ??????idx???????????\??£??????
    pleft = ino[:idx]
    pright = ino[idx+1:]
    prlen = len(pright)
    pllen = len(pleft)
    if prlen == 1:
        # ????????????pright??????????????????proot??????
        pright[0].parent = proot
        pright[0].depth = proot.depth + 1
        proot.right = pright[0]
    if pllen == 1:
        # ????????????pleft??????????????????proot??????
        pleft[0].parent = proot
        pleft[0].depth = proot.depth + 1
        proot.left = pleft[0]
    # ??°??????ino???????????????????????§????????????preo???????????£?????????
    if prlen > 1:
        for r in pright:
            r.parent = proot
            r.depth = proot.depth + 1
        pprt = rec(preo[1+pllen:], pright)
        proot.right = pprt
    if pllen > 1:
        for l in pleft:
            l.parent = proot
            l.depth = proot.depth + 1
        pprt = rec(preo[1:1+pllen], pleft)
        proot.left = pprt

    if prlen == 0: proot.right = None
    if pllen == 0: proot.left = None
    return proot

n = int(input())
nds = [Node(i+1) for i in range(n)] # id??????????????§??????(????????????)????????????id???1
preo = [nds[int(i)-1] for i in input().split()]
ino = [nds[int(i)-1] for i in input().split()]
# ????????°??¨??????????????\????????????????????°???????????±???????????????
root = rec(preo, ino)
from collections import deque
dq = deque()
# Postorder
visited = [None]*n
cnt = 0
dq.append(root)
while len(dq) > 0:
    pp = dq.pop()
    dl = pp.num_child()
    if dl == 0:
        visited[cnt] = pp
        cnt += 1
        continue
    if dl > 0:
        l,r = pp.left, pp.right
        if (l and l not in visited) or (r and r not in visited):
            if pp: dq.append(pp)
            if r: dq.append(r)
            if l: dq.append(l)
        else:
            visited[cnt] = pp
            cnt += 1
            continue

ss = ''
for v in visited: ss += ' '+str(v.id)
print(ss[1:])

Submission status: Runtime Error

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

d = []
root = pre[1]
pre = iter(pre).__next__

def dfs(l, r):
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    d += [c]
    
dfs(0, len(ino))
print(*c)

Submission status: Runtime Error

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

d = []
root = pre[1]
pre = iter(pre).__next__

def dfs(l, r):
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    d += [c]
    
dfs(0, len(ino))
print(*d)

Submission status: Runtime Error

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

d = []
root = pre[1]
pre = iter(pre).__next__

def dfs(l, r):
    global d
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    d += [c]
    
dfs(0, len(ino))
print(*d)

Submission status: Runtime Error

Solution code:
def postorder(n,preorder,inorder):
    if len(preorder) > 1:
        left_inorder = []
        right_inorder = []
        flag = False
        for i in range(len(inorder)):
            if flag == False:
                if n == inorder[i]:
                    flag = True
                else:
                    left_inorder.append(inorder[i])
            else:
                right_inorder.append(inorder[i])
        left_preorder = []
        right_preorder = []
        flag = False
        for i in range(1,len(preorder)):
            if flag == False:
                left_preorder.append(preorder[i])
                if len(left_preorder) == len(left_inorder):
                    flag = True
            else:
                right_preorder.append(preorder[i])
        postorder(left_preorder[0],left_preorder,left_inorder)
        postorder(right_preorder[0],right_preorder,right_inorder)
    if len(preorder) >= 0:
        print n,

n = int(raw_input())
preorder = map(int,raw_input().split(' '))
inorder = map(int,raw_input().split(' '))

postorder(preorder[0],preorder,inorder)

Submission status: Runtime Error

Solution code:
#coding:UTF-8

def RoT(A,B,ans):
    if A:
        root=A[0]
        rindex=B.index(root)
        Aleft=A[1:rindex+1]
        Aright=A[rindex+1:]
        Bleft=B[:rindex]
        Bright=B[rindex:]
        RoT(Aleft,Bleft,ans)
        RoT(Aright,Bright,ans)
        ans.append(root)
        
        


if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    B=input().split(" ")
    ans=[]
    RoT(A,B,ans)
    print(" ".join(ans))

Submission status: Runtime Error

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D

def postorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        postorder(binary_tree, left, result)
    if not right == -1:
        postorder(binary_tree, right, result)

    result.append(target_index)

def solve(preorder_list, inorder_list, result):
    if len(inorder_list) == 1:
        return inorder_list[0]
    #print(result)
    parent = preorder_list[0]

    left_trees = inorder_list[:inorder_list.index(parent)]
    right_tree_index = 1
    if left_trees:
        result[parent]["left"] = solve(preorder_list[1:], left_trees, result)
        right_tree_index = preorder_list.index(left_trees[-1])
        
    right_trees = inorder_list[inorder_list.index(parent) + 1:]
    if right_trees:
        result[parent]["right"] = solve(preorder_list[right_tree_index:], right_trees, result)

    return parent

def reconstruction(preorder_list, inorder_list, node_num):
    result = [{"left":-1,"right":-1} for i in range(node_num + 1)]
    solve(preorder_list, inorder_list, result)
    return result

def main():
    node_num = int(input())
    preorder_list = [int(a) for a in input().split()]
    inorder_list = [int(a) for a in input().split()]
    binary_tree = reconstruction(preorder_list, inorder_list, node_num)
    postorder_list = []
    postorder(binary_tree, preorder_list[0], postorder_list)
    print(*postorder_list)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D

def postorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        postorder(binary_tree, left, result)
    if not right == -1:
        postorder(binary_tree, right, result)

    result.append(target_index)

def solve(preorder_list, inorder_list, result):
    #print(preorder_list, inorder_list)
    if len(inorder_list) == 1:
        return inorder_list[0]
    
    parent = preorder_list[0]
    left_trees = inorder_list[:inorder_list.index(parent)]
    right_tree_index = 1
    if left_trees:
        result[parent]["left"] = solve(preorder_list[1:], left_trees, result)
        right_tree_index = preorder_list.index(left_trees[-1]) + 1
        
    right_trees = inorder_list[inorder_list.index(parent) + 1:]
    if right_trees:
        result[parent]["right"] = solve(preorder_list[right_tree_index:], right_trees, result)

    return parent

def reconstruction(preorder_list, inorder_list, node_num):
    result = [{"left":-1,"right":-1} for i in range(node_num + 1)]
    solve(preorder_list, inorder_list, result)
    return result

def main():
    node_num = int(input())
    preorder_list = [int(a) for a in input().split()]
    inorder_list = [int(a) for a in input().split()]
    binary_tree = reconstruction(preorder_list, inorder_list, node_num)
    postorder_list = []
    postorder(binary_tree, preorder_list[0], postorder_list)
    print(*postorder_list)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#Reconstruction of the Tree
n = int(input())
pre = list(map(int,input().split()))
ino = list(map(int,input().split()))

post=[]
i = -1
def recaonstruction(l, r):
    global i
    if l >= r:
        return
    i += 1
    c = pre[i]
    m = ino.index(c)
    reconstruction(l, m)
    reconstruction(m+1, r)
    post.append(c)
reconstruction(0, n)
print(" ".join(map(str,post)))

Submission status: Runtime Error

Solution code:
# coding=utf-8
from collections import deque

def reconstruction(left, right):
    global pre_order
    global in_order
    global post_order
    global n

    if left > right:
        return None
    elif left == right:
        root = pre_order.popleft()
        post_order.append(root)
        return None
    else:
        root = pre_order.popleft()

    root_pos = in_order.index(root)
    reconstruction(left, root_pos-1)
    reconstruction(root_pos+1, right)
    post_order.append(root)

n = int(input())
pre_order = deque(map(int, input().split()))
in_order = deque(map(int, input().split()))
post_order = []

reconstruction(0, n-1)
print(*post_order)

Submission status: Runtime Error

Solution code:
I = 0
L = 1
R = 2
P = 3
B = 4
D = 5
H = 6

def search(N, A, B, num):
    """ N ??? Nodes A???Preorder?????? B???Inorder??????
        ??????????????????????????§??? root ??? index ????????? """
#    print(A)
#    print(B)
    root = A[0]
    ld = num
    for i in range(num):
        if B[i] == root:
            ld = i
            break
    if ld > 0:
        N[root][L] = search(N,A[1:ld+1],B[:ld],ld)
    rt = ld + 1
    if rt < num:
        N[root][R] = search(N,A[rt:],B[rt:],num - rt)
    return root

def getroot(A, id):
    if A[id][P] > -1:
        return getroot(A,A[id][P])
    return A[id][I]

def preorder(N,id,A):
    if id < 0:
        return
    A.append(id)
    preorder(N,N[id][L],A)
    preorder(N,N[id][R],A)

def inorder(N,id,A):
    if id < 0:
        return
    inorder(N,N[id][L],A)
    A.append(id)
    inorder(N,N[id][R],A)

def postorder(N,id,A):
    if id < 0:
        return
    postorder(N,N[id][L],A)
    postorder(N,N[id][R],A)
    A.append(id)


def main():

    """ ????????? """
    num = int(input().strip())
    plist = list(map(int,input().split()))
    ilist = list(map(int,input().split()))
    pos = []
    
    nodes = [[i, -1, -1, -1, -1, 0, 0] for i in range(num)]

    search(nodes,plist,ilist,num)
#    pre = [""]
#    ino = [""]
    pos = []

#    preorder(nodes,plist[0],pre)
#    inorder(nodes,plist[0],ino)
    postorder(nodes,plist[0],pos)

#    print("Preorder")
#    print(" ".join(map(str,pre)))
#    print("Inorder")
#    print(" ".join(map(str,ino)))
#    print("Postorder")
    print(" ".join(map(str,pos)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
I = 0
L = 1
R = 2
P = 3
B = 4
D = 5
H = 6

def getidx(Tree,value):
    idx = -1
    for i in range(len(Tree)):
        if Tree[i][I] == value:
            idx = i
            break
    return idx

def search(Tree, A, B, num):
    """ Tree ??? Tree A???Preorder?????? B???Inorder??????
        ??????????????????????????§??? root ??? index ????????? """
    root = A[0]
    rootidx = getidx(Tree,root)
    ld = num
    for i in range(num):
        if B[i] == root:
            ld = i
            break
    if ld > 0:
        left,lidx = search(Tree,A[1:ld+1],B[:ld],ld)
        Tree[rootidx][L] = lidx
    rt = ld + 1
    if rt < num:
        right,ridx = search(Tree,A[rt:],B[rt:],num - rt)
        Tree[rootidx][R] = ridx
    return (root,rootidx)

def getroot(Tree, nidx):
    pidx = Tree[nidx][P]
    if pidx < 0:
        return nidx
    return getroot(Tree,pidx)

ef postorder(Tree, nidx, A):
    if nidx < 0:
        return
    postorder(Tree,Tree[nidx][L],A)
    postorder(Tree,Tree[nidx][R],A)
    A.append(Tree[nidx][I])


def main():

    """ ????????? """
    num = int(input().strip())
    plist = list(map(int,input().split()))
    ilist = list(map(int,input().split()))
    tree = []
    for i in plist:
        tree.append([i, -1, -1, -1, -1, 0, 0])

    root,ridx = search(tree, plist, ilist, num)

    pos = []

    postorder(tree, ridx, pos)
    print(" ".join(map(str,pos)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [None for i in range(n +1)]
list_pre = list(map(int, input().split()))
list_in = list(map(int, input().split()))
 
 
def reconstruct(tree_pre, tree_in):
    if not tree_pre:
        return -1
    root = tree_pre[0]
    idx = tree_in.index(root)
    tree[root] = (reconstruct(tree_pre[1:i + 1], tree_in[:i]), 
                  reconstruct(tree_pre[i + 1:],  tree_in[i + 1:]))
    return root


def post_order_search(i):
    if i == -1:
        return
    l, r = tree[i]
    for j in post_order_search(l):
        yield j
    for j in post_order_search(r):
        yield j
    yield i


solve(list_pre, list_in)

print(*postorder(list_pre[0]))

Submission status: Runtime Error

Solution code:
#coding:utf-8
N = int(input())
preList = "".join(list(input().split()))
inList = "".join(list(input().split()))

def recon(l,r):
    if l >= r:
        return
    global pos
    c = preList[pos]
    index = inList.find(c)
    pos += 1
    recon(l,index)
    recon(index+1,r)
    
    global answer
    answer.append(c)

answer = []
pos = 0
recon(0,N)

answer = " ".join(answer)
print(answer)

Submission status: WA: Presentation Error

Solution code:
def postorder(preo,ino):
    if preo:
        root = preo[0]
        inroot = ino.index(root)
        leftpre = preo[1:inroot+1]
        leftin = ino[:inroot]
        rightpre = preo[inroot+1:]
        rightin = ino[inroot+1:]
        postorder(leftpre,leftin)
        postorder(rightpre,rightin)
        post.append(root)

index = int(input())
preorder = [int(n) for n in input().split(' ')]
inorder = [int(n) for n in input().split(' ')]
post = []
postorder(preorder,inorder)
for p in range(index):
    print(post[p],end=" ")

Submission status: WA: Presentation Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
preorder & inorder

5
1 2 3 4 5
3 2 4 1 5

9
1 2 3 4 5 6 7 8 9
3 2 5 4 6 1 8 7 9

output:
postorder
3 4 2 5 1
"""

import sys


# recursively defines a binary tree
# node.left or node.right may also be a binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


def reconstruction(_pre_order, _in_order):
    # write your code here
    if not _pre_order:
        return None
    root = TreeNode(_pre_order[0])
    root_position = _in_order.index(_pre_order[0])
    root.left = reconstruction(_pre_order=_pre_order[1:1 + root_position], _in_order=_in_order[:root_position])
    root.right = reconstruction(_pre_order=_pre_order[root_position + 1:], _in_order=_in_order[root_position + 1:])
    print(root.val, end=' ')
    # post_order.append(root.val)
    return root.val


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    pre_order = list(map(int, _input[1].split()))
    in_order = list(map(int, _input[2].split()))
    # assert len(pre_order) == len(in_order) == array_length

    # post_order = []
    reconstruction(_pre_order=pre_order, _in_order=in_order)
    print('')
    # print(*post_order)

Submission status: WA: Presentation Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
preorder & inorder

5
1 2 3 4 5
3 2 4 1 5

9
1 2 3 4 5 6 7 8 9
3 2 5 4 6 1 8 7 9

output:
postorder
3 4 2 5 1
"""

import sys


# recursively defines a binary tree
# node.left or node.right may also be a binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


def reconstruction(_pre_order, _in_order):
    # write your code here
    if not _pre_order:
        return None
    root = TreeNode(_pre_order[0])
    root_position = _in_order.index(_pre_order[0])
    root.left = reconstruction(_pre_order=_pre_order[1:1 + root_position], _in_order=_in_order[:root_position])
    root.right = reconstruction(_pre_order=_pre_order[root_position + 1:], _in_order=_in_order[root_position + 1:])
    print(root.val, end=' ')
    # post_order.append(root.val)
    return root.val


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    pre_order = list(map(int, _input[1].split()))
    in_order = list(map(int, _input[2].split()))
    # assert len(pre_order) == len(in_order) == array_length

    # post_order = []
    reconstruction(_pre_order=pre_order, _in_order=in_order)
    # print('')
    # print(*post_order)

Submission status: WA: Presentation Error

Solution code:
class Tree:
    __slots__ = ['id', 'p', 'left', 'right']
    def __init__(self, id):
        self.id = id
        self.left = -1
        self.right = -1
    def setc(self, c):
        if self.left == -1:
            self.left = c
        else:
            self.right = c
    def __str__(self):
        return f"node {self.id}: left = {self.left}, right = {self.right}"
n = int(input())
tree = tuple(Tree(i) for i in range(n + 1))
pretree = list(map(int, input().split()))
inotree = list(map(int, input().split()))
root = pretree[0]
root_index = inotree.index(root)
SET = set(pretree) - {root}
def treeSet(A, i):
    if len(A) == 0:
        return
    global SET
    c = root
    r = pretree.index(A[0])
    for a in pretree[i: r + 1]:
        if c != a:
            SET -= {a}
            tree[c].setc(a)
            c = a
    for b in A[1:]:
        if b not in SET:
            c = b
            continue
        SET.add(b)
        tree[c].setc(b)
        c = b
treeSet(inotree[:root_index], 0)
treeSet(inotree[root_index + 1:], root_index + 1)
def postorder_tree_walk(id):
    if tree[id].left != -1:
        postorder_tree_walk(tree[id].left)
    if tree[id].right != -1:
        postorder_tree_walk(tree[id].right)
    print(f" {tree[id].id}", end="")
postorder_tree_walk(root)
print()

Submission status: WA: Presentation Error

Solution code:
class Tree:
    __slots__ = ['id', 'p', 'left', 'right']
    def __init__(self, id):
        self.id = id
        self.left = -1
        self.right = -1
    def setc(self, c):
        if self.left == -1:
            self.left = c
        else:
            self.right = c
    def __str__(self):
        return f"node {self.id}: left = {self.left}, right = {self.right}"
n = int(input())
tree = tuple(Tree(i) for i in range(n + 1))
pretree = list(map(int, input().split()))
inotree = list(map(int, input().split()))
root = pretree[0]
root_index = inotree.index(root)
SET = set(pretree) - {root}
def treeSet(A, i):
    if len(A) == 0:
        return
    global SET
    c = root
    r = pretree.index(A[0])
    for a in pretree[i: r + 1]:
        if c != a:
            SET -= {a}
            tree[c].setc(a)
            c = a
    for b in A[1:]:
        if b not in SET:
            c = b
            continue
        SET.add(b)
        tree[c].setc(b)
        c = b
treeSet(inotree[:root_index], 0)
treeSet(inotree[root_index + 1:], root_index + 1)
def postorder_tree_walk(id):
    if tree[id].left != -1:
        postorder_tree_walk(tree[id].left)
    if tree[id].right != -1:
        postorder_tree_walk(tree[id].right)
    print(f" {tree[id].id}", end="")
postorder_tree_walk(root)

Submission status: WA: Presentation Error

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):
    if ns[i].left != -1:
        postorder(ns, ns[i].left)
    if ns[i].right != -1:
        postorder(ns, ns[i].right)
    print(" " + str(i + 1), end ="")

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[1 + i]].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 i in range(n)]

poio_node(ns, po, io)

postorder(ns, po[0])
print()

Submission status: WA: Presentation Error

Solution code:
INF = 10**3


def reconstruction(p_ary, i_ary, l, r):
    if l >= r:
        return

    c = INF
    for i in i_ary[l:r]:
        ind = p_ary.index(i)
        if ind < c:
            c = i
    m = i_ary.index(c)

    reconstruction(p_ary, i_ary, l, m)
    reconstruction(p_ary, i_ary, m + 1, r)

    print(c, end=' ')


n = int(input())
p_ary = [int(_) for _ in input().split()]
i_ary = [int(_) for _ in input().split()]
reconstruction(p_ary, i_ary, 0, n)