Problem:
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

Solution (Python):
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)))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):



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)

Solution (Python):
postorder = []

def printpostorder(inorder, preorder, n): 
    if preorder[0] in inorder: 
        root = inorder.index(preorder[0]) 
          
    if root != 0: 
        printpostorder(inorder[:root],  
                       preorder[1:root + 1],  
                       len(inorder[:root])) 
      
    if root != n - 1: 
        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 ]))

Solution (Python):



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)

Solution (Python):
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)

Solution (Python):
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())) 
    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(str(root))

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

Solution (Python):
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))

Solution (Python):




import sys
sys.setrecursionlimit(10**9)  


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)

Solution (Python):
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)))

Solution (Python):
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)))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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 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()

Solution (Python):


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))

Solution (Python):
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]
    
    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)))

Solution (Python):
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(']', ''))

Solution (Python):
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()

Solution (Python):

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

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

    mid = ino.index(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)))

Solution (Python):
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[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)

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

Solution (Python):
n = int(input())
preorder_list = list(map(int,input().split()))
inorder_list = list(map(int,input().split()))
postorder_list = []
cnt = 0
def make_postorder_list(arg_postorder_list, arg_tmp_lst):
    global cnt
    tmp_cnt = cnt
    root = arg_tmp_lst.index(preorder_list[cnt])
    left_lst = arg_tmp_lst[:root]
    right_lst = arg_tmp_lst[root+1:]
    if cnt+1<=n-1:
        if preorder_list[cnt+1] in left_lst:
            cnt+=1
            make_postorder_list(arg_postorder_list, left_lst)
    if cnt+1<=n-1:
        if preorder_list[cnt+1] in right_lst:
            cnt+=1
            make_postorder_list(arg_postorder_list, right_lst)
    arg_postorder_list.append(preorder_list[tmp_cnt])
    

make_postorder_list(postorder_list, inorder_list)

print(*postorder_list)

Solution (Python):


import sys
sys.setrecursionlimit(2**20)  


class Node:
    def __init__(self,
                 parent=None,
                 left=None,
                 right=None):
        self.parent = parent
        self.left = left  
        self.right = right  



def post_parse(T, u, post_ls):
    if u == None:
        return
    post_parse(T, T[u].left, post_ls)
    post_parse(T, T[u].right, post_ls)
    post_ls.append(u)



N = int(input())
pre_ls = list(map(int, input().split()))
in_ls = list(map(int, input().split()))
root_pos = 0
ROOT = pre_ls[root_pos]
T = {key+1: Node() for key in range(N)}




def rec(l: int, r: int, root_pos: int):
    '''
    l,rはin_lsに対して範囲を指定するidx
    l:rであり、半開区間
    root_posはpre_lsにおけるrootのidx。本では木の左下から復元するのを前提に実装していたが、
    ここではどういう順番で復元しても大丈夫なように実装する。
    '''
    
    if r-l <= 1:  
        return
    root = pre_ls[root_pos]
    mid = in_ls.index(root)  

    
    
    if mid != l:
        root_pos_left = root_pos+1  
        T[pre_ls[root_pos]].left = pre_ls[root_pos_left]
        T[pre_ls[root_pos_left]].parent = pre_ls[root_pos]
        
        rec(l, mid, root_pos_left)
    
    if mid != r-1:  
        root_pos_right = root_pos+1+mid-l  
        T[pre_ls[root_pos]].right = pre_ls[root_pos_right]
        T[pre_ls[root_pos_right]].parent = pre_ls[root_pos]
        rec(mid+1, r, root_pos_right)



rec(0, N, root_pos)





post_ls = []
post_parse(T, ROOT, post_ls)

print(*post_ls)

Solution (Python):
class Node:
	def __init__(self):
		self.parent = None
		self.left = None
		self.right = None

def restoreTree(preList, inList):
	root = preList[0]
	index = inList.index(root)
	leftin = inList[:index]
	
	rightin = inList[index + 1:]
	
	num_left = len(leftin)
	num_right = len(rightin)
	if num_left != 0:
		leftpre = preList[1:1 + num_left]
		
		left_root = leftpre[0]
		T[root].left = left_root
		T[left_root].parent = root
		restoreTree(leftpre, leftin)
	if num_right != 0:
		rightpre = preList[1 + num_left:]
		
		right_root = rightpre[0]
		T[root].right = right_root
		T[right_root].parent = root
		restoreTree(rightpre, rightin)


def postOrder(root):
	if T[root].left is not None:
		postOrder(T[root].left)
	if T[root].right is not None:
		postOrder(T[root].right)
	L.append(str(root))

if __name__ == "__main__":
	n = int(input())
	T = []
	for _ in range(n + 1):
		T.append(Node())
	preList = list(map(int, input().split()))
	inList = list(map(int, input().split()))
	root = preList[0]
	restoreTree(preList, inList)
	L = []
	postOrder(root)
	print(" ".join(L))

Solution (Python):




class Node:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right

    def __iter__(self):
        yield from self.postorder()

    def postorder(self):
        yield from self.left
        yield from self.right
        yield self


def reconstruct(preorder, inorder):
    if len(preorder) == 0:
        return []

    root_val = preorder[0]
    root_index = inorder.index(root_val)
    inorder_left = inorder[:root_index]
    inorder_right = inorder[root_index + 1 :]
    preorder_left = [x for x in preorder if x in inorder_left]
    preorder_right = [x for x in preorder if x in inorder_right]

    return Node(
        root_val,
        reconstruct(preorder_left, inorder_left),
        reconstruct(preorder_right, inorder_right),
    )


def main():
    n = int(input())
    preorder = [int(x) for x in input().split()]
    inorder = [int(x) for x in input().split()]

    print(*[node.val for node in reconstruct(preorder, inorder).postorder()])


main()

Solution (Python):
def reconstruction(l, r, pre, _in, result):
    if l >= r:
        return
    c = pre[0]
    del pre[0]
    m = _in.index(c)
    reconstruction(l, m, pre, _in, result)
    reconstruction(m+1, r, pre, _in, result)
    result.append(str(c))


def main():
    n = int(input())
    pre_order = list(map(int, input().split(' ')))
    in_order = list(map(int, input().split(' ')))
    ans = []
    reconstruction(0, n, pre_order, in_order, ans)
    print(' '.join(ans))


if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1


def reconstruction(preo, ino):
    root = preo[0]

    ileft = ino[0:ino.index(root)]
    iright = ino[ino.index(root)+1:]

    pleft = preo[1:]
    pright = preo[1:]

    for item in iright:
        pleft.remove(item)

    for item in ileft:
        pright.remove(item)

    if len(pleft) == 0:
        pass
    elif len(pleft) == 1:
        Nodes[root-1].left = pleft[0]
    else:
        Nodes[root-1].left = reconstruction(pleft, ileft)

    if len(pright) == 0:
        pass
    elif len(pright) == 1:
        Nodes[root-1].right = pright[0]
    else:
        Nodes[root-1].right = reconstruction(pright, iright)

    return root


def postorder(id):
    if Nodes[id-1].left != -1:
        postorder(Nodes[id-1].left)

    if Nodes[id-1].right != -1:
        postorder(Nodes[id-1].right)

    ans.append(id)


def main():
    n = int(input())
    global Nodes
    Nodes = [Node() for i in range(n)]

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

    rootid = reconstruction(preorder, inorder)

    global ans
    ans = []
    postorder(rootid)
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
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):
    root = po[0]
    i = io.index(root)
    if i!=0: 
        ns[po[0]].left = po[1]
        ns[po[1]].parent = po[0]
        poio_node(ns,po[1:i+1],io[:i]) 
    if i!=len(io)-1: 
        ns[po[0]].right = po[i+1]
        ns[po[i+1]].parent = po[0]
        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)

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

Solution (Python):
from typing import List


def reconstruct_trees(preordered_list: List[int],
                      inordered_list: List[int], node: int) -> None:
    global trees
    in_node_index = inordered_list.index(node)
    in_left_list = inordered_list[:in_node_index]
    in_right_list = inordered_list[in_node_index + 1:]
    _ = preordered_list.index(node)
    pr_left_list = preordered_list[1: 1 + len(in_left_list)]
    pr_right_list = preordered_list[1 + len(in_left_list):]

    if 0 == len(in_left_list):
        pass
    else:
        next_node = pr_left_list[0]
        trees[next_node]['parent'] = node
        trees[node]['left-child'] = next_node
        if 1 < len(in_left_list):
            reconstruct_trees(pr_left_list, in_left_list, next_node)
    if 0 == len(in_right_list):
        pass
    else:
        next_node = pr_right_list[0]
        trees[next_node]['parent'] = node
        trees[node]['right-child'] = next_node
        if 1 < len(in_right_list):
            reconstruct_trees(pr_right_list, in_right_list, next_node)


def create_postorder(node: int) -> None:
    global trees
    global postordered_list
    left_child = trees[node]['left-child']
    right_child = trees[node]['right-child']
    if -1 != left_child:
        create_postorder(left_child)
    if -1 != right_child:
        create_postorder(right_child)
    postordered_list.append(node)


if __name__ == "__main__":
    node_num = int(input())
    trees = {idx + 1:
             {"parent": -1, "left-child": -1, "right-child": -1}
             for idx in range(node_num)}
    preordered_list = list(map(lambda x: int(x), input().split()))
    inordered_list = list(map(lambda x: int(x), input().split()))
    postordered_list = []  

    root_node = preordered_list[0]

    reconstruct_trees(preordered_list, inordered_list, root_node)
    create_postorder(root_node)

    print(" ".join([str(elem) for elem in postordered_list]))

Solution (Python):
pos = 0
postorder = []
def reconstruction(l, r):
    global pos
    global postorder
    if l >= r:
        return
    
    c = preorder[pos]
    m = inorder.index(c)
    pos += 1
   
    
    reconstruction(l, m)
    
    reconstruction(m + 1, r)
    postorder.append(c)

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

reconstruction(0, n)
print(" ".join(map(str, postorder)))

Solution (Python):
index = 0
answer = []


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

    global index, answer

    node_mid = preorder[index]
    index += 1
    mid = inorder.index(node_mid)

    postorder_treewalk(left, mid)
    postorder_treewalk(mid + 1, right)
    answer += [node_mid]



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


postorder_treewalk(0, n)
print(*answer)

Solution (Python):
def postorder(pre,inor):
    if len(pre) <= 1:
        return pre
    else:
        root = pre[0]
        i = inor.index(root)
        leftin = inor[:i]
        leftpre = pre[1:i+1]
        rightin = inor[i+1:]
        rightpre = pre[i+1:]
        left = postorder(leftpre,leftin)
        right = postorder(rightpre,rightin)
        return left+right+[root]
n = str(input())
pre = list(map(str,input().split()))
inor = list(map(str,input().split()))
print(" ".join(postorder(pre,inor)))

Solution (Python):
class Tree:
    def __init__(self, *args):
        self.value, self.left, self.right = args

    def postorder(self):
        left = [] if self.left is None else self.left.postorder()
        right = [] if self.right is None else self.right.postorder()
        return left + right + [self.value]


def recover(pre, ino):
    preord = dict(map(lambda t: (t[1], t[0]), enumerate(pre)))

    def make_tree(tree):
        if len(tree) == 0:
            return None
        root_idx, root_value = min(enumerate(tree), key=lambda t: preord[t[1]])
        return Tree(
            root_value,
            make_tree(tree[:root_idx]),
            make_tree(tree[root_idx + 1:])
        )

    return make_tree(ino).postorder()


if __name__ == '__main__':
    _ = input()
    pre = list(map(int, input().split()))
    ino = list(map(int, input().split()))
    print(' '.join([str(t) for t in recover(pre, ino)]))