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 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.pop(0)
        post_order.append(root)
        return None
    else:
        root = pre_order.pop(0)

    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 = list(map(int, input().split()))
in_order = list(map(int, input().split()))
post_order = []

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

Solution (Python):
def reconstruction(l, r):
    global i
    if l >= r:
        return
    c = PRE[i]
    i += 1
    m = IN.index(c)
    reconstruction(l, m)
    reconstruction(m + 1, r)
    POST.append(c)


if __name__ == "__main__":
    n = int(input())
    PRE = list(map(int, input().split()))
    IN = list(map(int, input().split()))
    POST = []
    i = 0
    reconstruction(0, n)
    print(" ".join(map(str, POST)))

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

Solution (Python):
def get_postorder(preorder, inorder):
    if not preorder:
        return []

    root = preorder[0]
    root_index = inorder.index(root)
    result = []

    result.extend(get_postorder(preorder[1:root_index+1], inorder[:root_index]))
    result.extend(get_postorder(preorder[root_index+1:], inorder[root_index+1:]))
    result.append(root)

    return result


if __name__ == '__main__':
    n = int(input())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))

    print(*get_postorder(preorder, inorder))

Solution (Python):
def getPostorder(preorder, inorder):
    if not preorder:
        return []
    postorder = []
    root = preorder[0]
    rootIndex = inorder.index(root)

    postorder.extend(getPostorder(preorder[1:rootIndex + 1], inorder[:rootIndex]))
    postorder.extend(getPostorder(preorder[rootIndex + 1:], inorder[rootIndex + 1:]))
    postorder.append(root)

    return postorder 

if __name__ == '__main__':
    n = int(input())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    print(*getPostorder(preorder, inorder))

Solution (Python):
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 solve(tree_pre, tree_in):
    if not tree_pre:
        return -1
    root = tree_pre[0]
    idx = tree_in.index(root)
    tree[root] = (solve(tree_pre[1:idx + 1], tree_in[:idx]), 
                  solve(tree_pre[idx + 1:],  tree_in[idx + 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(*post_order_search(list_pre[0]))

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


def reconstruct(x, y):
    top = x[0]
    root = Node(top)
    

    mid = y.index(top)
    left = y[:mid]
    right = y[mid+1:]
    if len(left) > 0:
        root.left = reconstruct(x[1:mid+1], left)
    if len(right) > 0:
        root.right = reconstruct(x[mid+1:], right)

    return root


def postorder(L, node):
    if node is None:
        return
    postorder(L, node.left)
    postorder(L, node.right)
    L.append(node.x)


if __name__ == "__main__":
    input()
    preorder = input().split()
    inorder = input().split()
    root = reconstruct(preorder, inorder)
    L = []
    postorder(L, root)
    print(' '.join(L))

Solution (Python):



def reconstruction(n, preorder, inorder):
    result = []

    def rec(preorder, inorder):
        if preorder == [] or inorder == []:
            pass
        else:
            index = inorder.index(preorder[0]) + 1
            rec(preorder[1:index], inorder[0:index-1])
            rec(preorder[index:], inorder[index:])
            result.append(str(preorder[0]))

    rec(preorder, inorder)
    print(" ".join(result))


if __name__ == "__main__":
    n = int(input())
    preorder = [int(x) for x in input().split()]
    inorder = [int(x) for x in input().split()]
    reconstruction(n, preorder, inorder)

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(100000)


if __name__ == '__main__':

    n = int(input())
    pre = deque([int(i) for i in input().split(" ")])
    ino = deque([int(i) for i in input().split(" ")])

    post = []
    def reconstruction(l, r):
        if l >= r:
            return
        c = pre.popleft()
        m = ino.index(c)
        reconstruction(l, m)
        reconstruction(m+1, r)
        
        post.append(c)

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

Solution (Python):
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()))
m = {a:i for i, a in enumerate(pretree)}
inotree = list(map(int, input().split()))
root = pretree[0]
def treeSet(A, id):
    if A == []:
        return -1
    elif len(A) == 1:
        return A[0]
    min_A_index = A.index(id)
    global tree
    if 0 < min_A_index:
        min_A = min(A[:min_A_index], key=lambda x: m[x])
        left = treeSet(A[:min_A_index], min_A)
        tree[id].left = left
    if 0 < len(A) - min_A_index - 1:
        min_A = min(A[min_A_index + 1:], key=lambda x: m[x])
        right = treeSet(A[min_A_index + 1:], min_A)
        tree[id].right = right
    return id
treeSet(inotree, root)
ans = []
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)
    global ans
    ans.append(id)
postorder_tree_walk(root)
print(*ans)

Solution (Python):
n = int(input())
pretree = list(map(int, input().split()))
inotree = list(map(int, input().split()))
def get_postorder(pre, ino):
    if not pre:
        return []
    root = pre[0]
    root_index = ino.index(root)
    result = []
    result.extend(get_postorder(pre[1:root_index + 1], ino[:root_index]))
    result.extend(get_postorder(pre[root_index + 1:], ino[root_index + 1:]))
    result.append(root)
    return result
print(*get_postorder(pretree, inotree))

Solution (Python):
class Node:

    def __init__(self, n):
        self.id = n
        self.left = None
        self.right = None

class BTree:

    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n + 1)]

    def make_tree(self, preorder, inorder):
        if preorder:
            root = preorder[0]
            i_root = inorder.index(root)
            inorder_left = inorder[:i_root]
            inorder_right = inorder[i_root + 1:]
            leftn = len(inorder_left)
            preorder_left = preorder[1:leftn + 1]
            preorder_right = preorder[leftn + 1:]

            self.nodes[root].left = self.make_tree(preorder_left, inorder_left)
            self.nodes[root].right = self.make_tree(preorder_right, inorder_right)

            return root

        else:
            return -1

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

if __name__ == '__main__':

    n = int(input())
    btree = BTree(n)

    preorder = [int(x) for x in input().split()]
    inorder = [int(x) for x in input().split()]

    btree.make_tree(preorder, inorder)

    result = btree.disp_postorder(preorder[0], [])
    print(" ".join([str(x) for x in result]))

Solution (Python):
def reconstract(l, r):
    if l >= r:
        return None

    c = next(root)
    m = in_hoge.index(c)
    
    reconstract(l, m)
    reconstract(m+1, r)
    
    post_hoge.append(c)

if __name__ == '__main__':
    _ = int(input())
    pre_hoge = [int(x) for x in input().split()]
    root = (x for x in pre_hoge)
    in_hoge = [int(x) for x in input().split()]
    post_hoge = list()
    
    reconstract(0, len(pre_hoge))
    
    print(' '.join([str(x) for x in post_hoge]))

Solution (Python):
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,p,i=int(input()),input().split(),input().split()
f(0,n);print(*a)

Solution (Python):
def reconstruct(pre, in_):
    if not pre:
        return -1
    root = pre[0]
    i = in_.index(root)
    tree[root] = (reconstruct(pre[1 : i+1], in_[:i]), reconstruct(pre[i+1:], in_[i+1:]))
    return root

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

n = int(input())
tree = [None for i in range(n+1)]
pre_tree = list(map(int, input().split()))
in_tree = list(map(int, input().split()))
reconstruct(pre_tree, in_tree)
print(*postorder(pre_tree[0]))

Solution (Python):
class BinaryTree:
    class Node:
        def __init__(self, nid, left, right):
            self.id = nid
            self.left = left
            self.right = right

        def has_left(self):
            return self.left is not None

        def has_right(self):
            return self.right is not None

        def __str__(self):
            return str(self.id)

    @classmethod
    def create(cls, ids):
        nodes = {}
        def find(n, li):
            for e1, e2, e3 in li:
                if e1 == n:
                    return (e2, e3)
            raise ValueError()

        def _create(nid):
            if nid in nodes:
                return nodes[nid]
            if nid == -1:
                return None

            lid, rid = find(nid, ids)
            if lid == -1 and rid == -1:
                right = None
                left = None
            elif lid == -1:
                right = _create(rid)
                left = None
            elif lid == -1:
                right = None
                left = _create(lid)
            else:
                right = _create(rid)
                left = _create(lid)
            nodes[nid] = cls.Node(nid, left, right)
            return nodes[nid]

        def _root(nodeids):
            for nid in [n[0] for n in nodeids]:
                if all([lid != nid and rid != nid for _, lid, rid in nodeids]):
                    return nid

        root = _create(_root(ids))
        return cls(root)

    def __init__(self, root):
        self.root = root

    def preorder(self):
        def _preorder(node):
            yield node
            if node.has_left():
                yield from _preorder(node.left)
            if node.has_right():
                yield from _preorder(node.right)
        yield from _preorder(self.root)

    def inorder(self):
        def _inorder(node):
            if node.has_left():
                yield from _inorder(node.left)
            yield node
            if node.has_right():
                yield from _inorder(node.right)
        yield from _inorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node.has_left():
                yield from _postorder(node.left)
            if node.has_right():
                yield from _postorder(node.right)
            yield node
        yield from _postorder(self.root)

def reconstruct(preorder, inorder):
    """Reconstruct a binary tree from preorder list
    and inorder list of the tree.

    >>> tree = reconstruct([1, 2, 3, 4, 5], [3, 2, 4, 1, 5])
    >>> print(" ".join([str(node) for node in tree.postorder()]))
    3 4 2 5 1
    """
    def _first(li):
        if len(li) > 0:
            return li[0]
        else:
            return -1

    def _reconstruct(_pre, _in):
        assert(len(_pre) == len(_in))
        if len(_pre) == 0:
            return []
        if len(_pre) == 1:
            return [[_pre[0], -1, -1]]
        root, *pre = _pre
        i = _in.index(root)
        in1, in2 = _in[:i], _in[i+1:]
        pre1, pre2 = _pre[1:i+1], _pre[i+1:]
        return ([[root, _first(pre1), _first(pre2)]] +
                _reconstruct(pre1, in1) +
                _reconstruct(pre2, in2))

    return BinaryTree.create(_reconstruct(preorder, inorder))


def run():
    _ = int(input())
    preorder = [int(i) for i in input().split()]
    inorder = [int(i) for i in input().split()]

    tree = reconstruct(preorder, inorder)
    print(" ".join([str(n) for n in tree.postorder()]))


if __name__ == '__main__':
    run()

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):
from collections import deque


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


n = int(input())
pre_lst = deque(map(int, input().split()))
in_lst = list(map(int, input().split()))
post_lst = []


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

    c = pre_lst.popleft()
    m = in_lst.index(c)

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

    post_lst.append(c)
    return


def main():
    reconstruction(0, n)
    print(" ".join([str(i) for i in post_lst]))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
preorder = list(map(int, input().split(' ')))
inorder = list(map(int, input().split(' ')))
postorder = []
pos = 0

def solve():
    global pos
    pos = 0
    reconstruction(0, len(preorder))
    for i in range(n):
        if i: print(' ', end='')
        print(postorder[i], end='')
    print()

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

solve()

Solution (Python):
INF = 10**3


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

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

    reconstruction(o_ary, p_ary, i_ary, l, m)
    reconstruction(o_ary, p_ary, i_ary, m + 1, r)
    o_ary.append(c)


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

Solution (Python):
def reconstruct(pre_list, in_list):
    if len(pre_list) <= 1:
        return pre_list
    now = pre_list[0]
    split_place = in_list.index(now)
    pre_left = pre_list[1:split_place + 1]
    in_left = in_list[0:split_place]
    pre_right = pre_list[split_place + 1:]
    in_right = in_list[split_place + 1:]
    return reconstruct(pre_left, in_left) + reconstruct(pre_right, in_right) + [now]

def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x, end=" ")
    print(a[-1])


n = int(input())
pre_list = [int(x) for x in input().split()]
in_list = [int(x) for x in input().split()]

post_list = reconstruct(pre_list, in_list)
print_list_split_whitespace(post_list)

Solution (Python):

N = int(input())
preList = list(input().split())
inList = list(input().split())

def recon(l,r):
    if l >= r:
        return
    global pos
    c = preList[pos]
    index = inList.index(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)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
Pre = iter([int(x) for x in input().split()])
In = [int(x) for x in input().split()]
C = []

def Reconstruction(l, r):
    if l >= r:
        return
    c = next(Pre)
    m = In.index(c)
    Reconstruction(l, m)
    Reconstruction(m+1, r)
    C.append(c)

Reconstruction(0, n)
print(*C)

Solution (Python):
import sys
sys.setrecursionlimit(2**25)

n = int(input())
pre_ls = list(map(int, input().split()))
in_ls = list(map(int, input().split()))

pos = 0
post_ls = []

def rec(left: int, right: int):
    global pos
    if left >= right:
        return
    tmp_root = pre_ls[pos]
    pos += 1
    mid = in_ls.index(tmp_root)
    
    rec(left, mid)
    rec(mid+1, right)
    post_ls.append(tmp_root)


def solve():
    pos = 0
    rec(0, len(pre_ls))
    print(*post_ls)
solve()

Solution (Python):
def reconstruct(l, r):
    if l >= r:
        return
    root = pre_list.pop(0)
    center = in_list.index(root)
    reconstruct(l, center) 
    reconstruct(center+1, r) 
    ans_list.append(str(root))
    
N = int(input())
pre_list = list(map(int, input().split()))
in_list = list(map(int, input().split()))


ans_list = []
reconstruct(0, N)
print(" ".join(ans_list))

Solution (Python):
import sys
from collections import defaultdict

NIL = -1
n = int(input())
pre = list(map(int, sys.stdin.readline().split()))
ino = list(map(int, sys.stdin.readline().split()))
post = []

pos = 0

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

pos = 0

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

Solution (Python):


n=int(input())
preorder=[int(i)for i in input().split()]
inorder=[int(i)for i in input().split()]
post=[]
pos=0
def recon(left,right):
    global inorder
    global pos
    if left>=right:
        return
    root=preorder[pos]
    pos+=1
    mid=inorder.index(root)
    recon(left,mid)
    recon(mid+1,right)
    post.append(str(root))

recon(0,n)
print(" ".join(post))

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

    
    preorder = [int(i)-1 for i in input().strip().split()] 
    inorder = [int(i)-1 for i in input().strip().split()] 

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

        
        root = nodes[preorder[0]]
        
        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:]

        
        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)) 
    root = nodes[preorder[0]]
    postorder_walk(root)
    print(" ".join(postorder))


if __name__ == "__main__":
    main()

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

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

    

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

    

    return new_list


def main():

    lst = narabekae(_Pre, _In)

    print(*lst)


main()

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

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

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

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

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

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

    reconstruction(l, m)
    reconstruction(m+1, r)
    
    global pos
    pos += [c]

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

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

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

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

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

def rec(l):
    if len(l) == 0:
        return
    
    x = preorder.pop(0)
    for i in range(len(l)):
        if l[i] == x:
            
            rec(l[:i])
            rec(l[i+1:])
    postorder.append(x)
    return

rec(inorder)
print(*postorder)

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