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

class Node:
	def __init__(self, v):
		self.v = v
		self.l = self.r = None
		self.p = -1
	def __str__(self):
		return str(self.v)

def find_pos(a, v):
	for i in range(len(a)):
		if a[i] == v:
			return i
	return -1

def add_node(root, cur, ino):
	idx = find_pos(ino, cur.v)
	st = []
	st.append(root)
	while len(st) != 0:
		node = st.pop()
		if node.p == -1:
			node.p = find_pos(ino, node.v)
		if idx < node.p:
			if node.l == None:
				node.l = cur
				return
			else:
				st.append(node.l)
		else:
			if node.r == None:
				node.r = cur
				return
			else:
				st.append(node.r)		

def post_order(root):
	st = []
	cur = root
	last = None
	ret = ''
	while cur != None or len(st) != 0:
		if cur != None:
			st.append(cur)
			cur = cur.l
		else:
			peek = st[len(st)-1]
			if peek.r != None and peek.r != last:
				cur = peek.r
			else:
				if len(ret) != 0:
					ret += ' '
				ret += str(peek.v)
				last = st.pop()
	print(ret)

n = int(input())
preo = list(map(int, input().split()))
ino = list(map(int, input().split()))

r = preo[0]
root = Node(r)
for i in range(1, n):
	cur = Node(preo[i])
	add_node(root, cur, ino)

post_order(root)

Solution (Python):

class Node:
	def __init__(self, v):
		self.v = v
		self.l = self.r = None
		self.p = -1
	def __str__(self):
		return str(self.v)

def find_pos(a, v):
	for i in range(len(a)):
		if a[i] == v:
			return i
	return -1

def add_node(root, cur, ino):
	idx = find_pos(ino, cur.v)
	st = []
	st.append(root)
	while len(st) != 0:
		node = st.pop()
		if node.p == -1:
			node.p = find_pos(ino, node.v)
		if idx < node.p:
			if node.l == None:
				node.l = cur
				return
			else:
				st.append(node.l)
		else:
			if node.r == None:
				node.r = cur
				return
			else:
				st.append(node.r)		

def post_order(root):
	st = []
	cur = root
	last = None
	ret = ''
	while cur != None or len(st) != 0:
		if cur != None:
			st.append(cur)
			cur = cur.l
		else:
			peek = st[len(st)-1]
			if peek.r != None and peek.r != last:
				cur = peek.r
			else:
				if len(ret) != 0:
					ret += ' '
				ret += str(peek)
				last = st.pop()
	return ret

n = int(input())
preo = list(map(int, input().split()))
ino = list(map(int, input().split()))

r = preo[0]
root = Node(r)
for i in range(1, n):
	cur = Node(preo[i])
	add_node(root, cur, ino)

print(post_order(root))

Solution (Python):
class Node:
	def __init__(self, v):
		self.v = v
		self.l = self.r = None
		self.p = -1
	def __str__(self):
		return str(self.v)

def find_pos(a, v):
	for i in range(len(a)):
		if a[i] == v:
			return i
	return -1

def add_node(root, cur, ino):
	cur.p = find_pos(ino, cur.v)
	st = []
	st.append(root)
	while len(st) != 0:
		node = st.pop()
		if node.p == -1:
			node.p = find_pos(ino, node.v)
		if cur.p < node.p:
			if node.l == None:
				node.l = cur
				return
			else:
				st.append(node.l)
		else:
			if node.r == None:
				node.r = cur
				return
			else:
				st.append(node.r)		

def post_order(root):
	st = []
	cur = root
	last = None
	ret = ''
	while cur != None or len(st) != 0:
		if cur != None:
			st.append(cur)
			cur = cur.l
		else:
			peek = st[len(st)-1]
			if peek.r != None and peek.r != last:
				cur = peek.r
			else:
				if len(ret) != 0:
					ret += ' '
				ret += str(peek)
				last = st.pop()
	return ret

n = int(input())
preo = list(map(int, input().split()))
ino = list(map(int, input().split()))
root = Node(preo[0])
for i in range(1, n):
	add_node(root, Node(preo[i]), ino)
print(post_order(root))

Solution (Python):
from collections import deque

def print_postorder(A, B, n):
    C = []
    def reconstruction(l, r):
        if l >= r:
            return
        c = A.popleft()
        m = B.index(c)
        reconstruction(l, m)
        reconstruction(m + 1, r)
        C.append(c)

    reconstruction(0, n)
    print(*C, sep=" ")

n = int(input())
A = deque([int(i) for i in input().split()])
B = [int(i) for i in input().split()]
print_postorder(A, B, n)

Solution (Python):

"""
Created on Sat Mar  2 15:32:11 2019

@author: Yamazaki Kenichi
"""

N = int(input())
pre = list(map(int,input().split()))
ino = list(map(int,input().split()))

tree = [[-1,-1,-1] for i in range(N+1)]
def make_tree(pre,ino):
    if len(pre)==0:
        return
    indx = ino.index(pre[0])
    if indx > 0:
        tree[pre[0]][1] = pre[1]
        tree[pre[1]][0] = pre[0]
        make_tree(pre[1:indx+1],ino[:indx])
    if indx != len(ino)-1:
        tree[pre[0]][2] = pre[indx+1]
        tree[pre[indx+1]][0] = pre[0]
        make_tree(pre[indx+1:],ino[indx+1:])
make_tree(pre,ino)

def pos(u,tree):
    res = []
    if tree[u][1] != -1:
        res += pos(tree[u][1],tree)
    if tree[u][2] != -1:
        res += pos(tree[u][2],tree)
    res += [str(u)]
    return res
ans = pos(pre[0],tree)
print(' '.join(ans))

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

d = []
root = pre[0]
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)

Solution (Python):
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])
    def root(self):
        for node in self.nodes.values():
            if node and node.nodetype() == 'root':
                return node
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        self.update_height()
        
        for child in self.children():
            child.parent = self
            child.update_depth()
    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()
            
    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()
                
    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'
    def degree(self):
        return len(self.children())
    
    def children(self):
        return [child for child in [self.left, self.right] if child]
    
    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode

def make_tree(tree, preorder, inorder):
    if len(preorder) == 0:
        return -1
    root_id = preorder[0]    
    root_index = inorder.index(root_id)
    left_id = make_tree(tree, preorder[1:root_index + 1], inorder[:root_index])
    right_id = make_tree(tree, preorder[root_index + 1:], inorder[root_index + 1:])
    tree.add_child(root_id, left_id, right_id)
    return root_id
    
n = int(input())
preorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

tree = Tree()
root_id = make_tree(tree, preorder, inorder)

print(*[node.id for node in tree.nodes[root_id].walk('Postorder')])

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

def postorder_tree_walk(root):
    result = []
    if root.left != None:
        result.extend(postorder_tree_walk(root.left))
    if root.right != None:
        result.extend(postorder_tree_walk(root.right))
    result.append(root.id)
    return result

def make_tree(root, left_ids, right_ids, tree, pre):
    if len(left_ids) == 1:
        root.left = tree[left_ids[0]]
    elif len(left_ids) > 1:
        root_id = 0
        for x in pre:
            if x in left_ids:
                root_id = x
                break
        index = left_ids.index(root_id)
        root.left = tree[root_id]
        make_tree(tree[root_id], left_ids[:index], left_ids[index + 1:], tree, pre)

    if len(right_ids) == 1:
        root.right = tree[right_ids[0]]
    elif len(right_ids) > 1:
        root_id = 0
        for x in pre:
            if x in right_ids:
                root_id = x
                break
        index = right_ids.index(root_id)
        root.right = tree[root_id]
        make_tree(tree[root_id], right_ids[:index], right_ids[index + 1:], tree, pre)

n = int(raw_input())
tree = [Node(i) for i in xrange(n+1)]
tree[0] = None
pre = map(int, raw_input().split())
inoder = map(int, raw_input().split())
root = tree[pre[0]]
index = inoder.index(root.id)
make_tree(root, inoder[:index], inoder[index + 1:], tree, pre)
result = postorder_tree_walk(root)
print ' '.join(map(str, result))

Solution (Python):
n = int(input())
tree = [None] * (n + 1)
preot = list(map(int, input().split()))
inot = list(map(int, input().split()))


def reconstruct(pretree, intree):
    if not pretree:
        return -1
    root = pretree[0]
    i = intree.index(root)
    tree[root] = (reconstruct(pretree[1:i + 1], intree[:i]), reconstruct(pretree[i + 1:], intree[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


reconstruct(preot, inot)

print(*postorder(preot[0]))

Solution (Python):
n = int(raw_input())
Pre = map(int,raw_input().split())
In = map(int,raw_input().split())

idx = 0

def reconstruction(l,r):
    global idx
    if l >= r:
        return
    c = Pre[idx]
    idx += 1
    m = In.index(c)
    reconstruction(l,m)
    reconstruction(m+1,r)

    print c,

def main():
    reconstruction(0,n)
    print 
    return 0

main()

Solution (Python):
def post_from_pre_in(preorder_elements, inorder_elements):
    if preorder_elements:
        global cnt
        root = preorder_elements[0]
        root_index = inorder_elements.index(root)
        preorder_left = preorder_elements[1:root_index+1]
        inorder_left = inorder_elements[:root_index]
        preorder_right = preorder_elements[root_index+1:]
        inorder_right = inorder_elements[root_index+1:]
        post_from_pre_in(preorder_left, inorder_left)
        post_from_pre_in(preorder_right, inorder_right)
        if cnt:
            print(root, end = ' ')
            cnt -= 1
        else:
            print(root)


cnt = int(input()) - 1

a = list(map(int, input().split()))
b = list(map(int, input().split()))

post_from_pre_in(a, b)

Solution (Python):
postorder_elements = []

def post_from_pre_in(preorder_elements, inorder_elements):
    if preorder_elements:
        root = preorder_elements[0]
        root_index = inorder_elements.index(root)
        preorder_left = preorder_elements[1:root_index+1]
        inorder_left = inorder_elements[:root_index]
        preorder_right = preorder_elements[root_index+1:]
        inorder_right = inorder_elements[root_index+1:]
        post_from_pre_in(preorder_left, inorder_left)
        post_from_pre_in(preorder_right, inorder_right)
        postorder_elements.append(root)



n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

post_from_pre_in(a, b)

print(*postorder_elements)

Solution (Python):


def post_order(id, list):
    if id > -1:
        post_order(node_dic[id].left, list)
        post_order(node_dic[id].right, list)
        list.append(id)

def gen_tree(root):
    i = iol.index(root)
    iol[i] = 0
    if iol[i-1] != 0:
        glt(root)
    if iol[i+1] != 0:
        grt(root)

def glt(root): 
    global p
    p += 1
    tmp = p
    i = iol.index(pol[p])
    gen_tree(pol[p])
    node_dic[root].left = pol[tmp]

def grt(root): 
    global p
    p += 1
    tmp = p
    i = iol.index(pol[p])
    gen_tree(pol[p])
    node_dic[root].right = pol[tmp]

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

n = int(raw_input())
node_dic = {}
for i in range(1, n+1):
    node_dic[i] = Node_Class(-1, -1)
pol = map(int, raw_input().split()) 
iol = map(int, raw_input().split()) 
iol.insert(n, 0)
iol.insert(0, 0)
p = 0
gen_tree(pol[p])
root = 0
for i in range(1, n+1):
    root += i
for i in range(1, n+1):
    left = node_dic[i].left
    right = node_dic[i].right
    if left > -1:
        root -= left
    if right > -1:
        root -= right
A = []
post_order(root, A)
print  " ".join(map(str, A))

Solution (Python):
import sys

def reconst(pre, ino):
    if len(pre) == 0:
        return
    elif len(pre) == 1:
        print pre[0],
        return

    root = ino.index(pre[0])
    preLeft, preRight = pre[1:root + 1], pre[root + 1:]
    inLeft, inRight = ino[:root], ino[root + 1:]

    reconst(preLeft, inLeft)
    reconst(preRight, inRight)
    print pre[0],

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    pre = map(int, lines[1].split())
    ino = map(int, lines[2].split())
    reconst(pre, ino)

Solution (Python):
import sys

def reconst(pre, ino):
    if len(pre) == 0:
        return
    elif len(pre) == 1:
        print pre[0],
        return

    root = ino.index(pre[0])
    preLeft, preRight = pre[1:root + 1], pre[root + 1:]
    inLeft, inRight = ino[:root], ino[root + 1:]

    reconst(preLeft, inLeft)
    reconst(preRight, inRight)
    print pre[0],

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    pre = map(int, lines[1].split())
    ino = map(int, lines[2].split())
    reconst(pre, ino)

Solution (Python):
from collections import namedtuple
Node = namedtuple('Node', ['parent', 'children'])
   
class my_binary_tree:
    def __init__(self, preorderList, inorderList):
        self.T = {}
        self.reconstruction(preorderList,inorderList)
   
    def reconstruction(self, preorderList, inorderList, parent=-1):
        i = preorderList[0]
        p = parent
        j = inorderList.index(i) 
        llen = len(inorderList[:j])
        rlen = len(inorderList[j+1:])
        if llen > 0: c0 = self.reconstruction(preorderList[1:llen+1],inorderList[:llen],i)
        else       : c0 = -1
        if rlen > 0: c1 = self.reconstruction(preorderList[llen+1:],inorderList[llen+1:],i)
        else       : c1 = -1
        self.T[i] = Node(p,[c0,c1])
        return i
   
    def getRoot(self, i=1):
        p = self.T[i].parent
        if p == -1: return i 
        return self.getRoot(p)
   
    def getPostorderList(self, i, L=[]):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        if c0 != -1: self.getPostorderList(c0, L)
        if c1 != -1: self.getPostorderList(c1, L)
        L.append(i)
        return L
   
    
if __name__=='__main__':
    n = int(input())
    preorderList = list(map(int,input().split()))
    inorderList  = list(map(int,input().split()))
    tree = my_binary_tree(preorderList,inorderList)
        
    r = tree.getRoot()
    print(*tree.getPostorderList(r))

Solution (Python):
from collections import namedtuple
Node = namedtuple('Node', ['parent', 'children'])
   
class my_binary_tree:
    def __init__(self, preorderList, inorderList):
        self.T = {}
        self.reconstruction(preorderList,inorderList)
   
    def reconstruction(self, preorderList, inorderList, parent=-1):
        i = preorderList[0]
        p = parent
        j = inorderList.index(i) 
        llen = len(inorderList[:j])
        rlen = len(inorderList[j+1:])
        if llen > 0: c0 = self.reconstruction(preorderList[1:llen+1],inorderList[:llen],i)
        else       : c0 = -1
        if rlen > 0: c1 = self.reconstruction(preorderList[llen+1:],inorderList[llen+1:],i)
        else       : c1 = -1
        self.T[i] = Node(p,[c0,c1])
        return i
   
    def getPostorderList(self, i):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        if c0 != -1: yield from self.getPostorderList(c0)
        if c1 != -1: yield from self.getPostorderList(c1)
        yield i
   
    
if __name__=='__main__':
    n = int(input())
    preorderList = list(map(int,input().split()))
    inorderList  = list(map(int,input().split()))
    tree = my_binary_tree(preorderList,inorderList)
        
    print(*tree.getPostorderList(preorderList[0]))

Solution (Python):
def postorder(preorder,inorder):
    if len(preorder) > 1:
        n = preorder[0]
        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:
                if len(left_preorder) == len(left_inorder):
                    flag = True
                else:
                    left_preorder.append(preorder[i])
            if flag == True:
                right_preorder.append(preorder[i])
        
        
        
        postorder(left_preorder,left_inorder)
        postorder(right_preorder,right_inorder)
    if len(preorder) > 0:
        print preorder[0],

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

postorder(preorder,inorder)

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

Solution (Python):
def reconsruction(pre, ino):
    if 0 == len(pre):
        return []
    else:
        root = pre[0]

        partition = ino.index(root)
        l_ino = ino[0:partition]
        r_ino = ino[partition+1:]

        pre_partition = len(l_ino)+1
        l_pre = pre[1:pre_partition]
        r_pre = pre[pre_partition:]

        return reconsruction(l_pre, l_ino) + reconsruction(r_pre, r_ino) + [root]

n = int(input())

t = [None] * n
pre = list(map(int, input().split()))
ino = list(map(int, input().split()))

print(*reconsruction(pre, ino))

Solution (Python):
def reconsruction(pre, ino):
    if 0 == len(pre):
        return []
    else:
        root = pre[0]

        partition = ino.index(root)
        l_ino = ino[0:partition]
        r_ino = ino[partition+1:]

        pre_partition = len(l_ino)+1
        l_pre = pre[1:pre_partition]
        r_pre = pre[pre_partition:]

        return reconsruction(l_pre, l_ino) + reconsruction(r_pre, r_ino) + [root]

n = int(input())

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

print(*reconsruction(pre, ino))

Solution (Python):


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+1:]
        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))

Solution (Python):


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]
    
    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 = len(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()

Solution (Python):



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


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


def reconstruction(_pre_order, _in_order):
    
    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:])
    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()))
    

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

Solution (Python):



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


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


def reconstruction(_pre_order, _in_order):
    
    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:])
    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()))
    

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

Solution (Python):



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




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


def reconstruction(_pre_order, _in_order):
    
    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:])
    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()))
    

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

Solution (Python):



"""
input:
5
1 2 3 4 5
3 2 4 1 5

output:
3 4 2 5 1
"""

import sys




class TreeNode:
    __slots__ = ('val', 'left', 'right')

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


def rec(pre_order, in_order, post_order):
    if not pre_order:
        return None, list()
    else:
        rt = TreeNode(pre_order[0])
        rt_pos = in_order.index(pre_order[0])
        rt.left = rec(pre_order[1:1 + rt_pos], in_order[:rt_pos], post_order)
        rt.right = rec(pre_order[rt_pos + 1:], in_order[rt_pos + 1:], post_order)

        
        post_order.append(rt.val)
        return rt, post_order


def solve():
    _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()))
    
    
    post_order = list()
    ans = rec(pre_order=pre_order, in_order=in_order, post_order=post_order)
    print(*ans[1])
    return None


if __name__ == '__main__':
    solve()

Solution (Python):

nil = -1

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

def post_tw(node, ans):
    if tree[node].left != nil:
        post_tw(tree[node].left, ans)

    if tree[node].right != nil:
        post_tw(tree[node].right, ans)

    ans.append(node + 1)

def reconst_tree(node, pretw_itr, subt):
    n_i = subt.index(node)

    left_subt = subt[:n_i]
    right_subt = subt[n_i + 1:]

    if left_subt:
        left = next(pretw_itr)
        tree[node].left = left
        reconst_tree(left, pretw_itr, left_subt)

    if right_subt:
        right = next(pretw_itr)
        tree[node].right = right
        reconst_tree(right, pretw_itr, right_subt)


n = int(input())
tree = [Node() for i in range(n)]

pretw = [int(i) - 1 for i in input().split()]
intw = [int(i) - 1 for i in input().split()]

pretw_itr = iter(pretw)

root = next(pretw_itr)

reconst_tree(root, pretw_itr, intw)

ans = []

post_tw(root, ans)

print(*ans)

Solution (Python):
def get_postorder(PRE, IN):
  if not PRE: return []

  result = []
  root = PRE[0]
  ri = IN.index(PRE[0])
  result.extend(get_postorder(PRE[1:ri+1], IN[:ri]))
  result.extend(get_postorder(PRE[ri+1:],  IN[ri+1:]))
  result.append(root)
  return result


N = int(input())
PRE = list(map(int, input().split()))
IN  = list(map(int, input().split()))
print(*get_postorder(PRE, IN))

Solution (Python):
def reconstruction(l, r):
    global P, I, post
    if l >= r:
        return
    c = P.pop(0)
    m = I.index(c)
    reconstruction(l, m)
    reconstruction(m + 1, r)
    post.append(c)


if __name__ == "__main__":
    n = int(input())
    P = list(map(int, input().split()))
    I = list(map(int, input().split()))
    post = []

    reconstruction(0, n)
    print(*post)

Solution (Python):
class Node:
    def __init__(self, num, left, right):
        self.value = num
        self.left = left
        self.right = right

EmptyTree = None

def make_node(num, left, right):
    return Node(num, left, right)

def value(tree):
    return tree.value

def left(tree):
    return tree.left

def right(tree):
    return tree.right

def is_empty(tree):
    return tree == EmptyTree

def make_leaf(num):
    return make_node(num, EmptyTree, EmptyTree)


def add_node(tree, x):
    if is_empty(tree):
        return make_leaf(x)
    elif x < value(tree):
        return make_node(value(tree), add_node(left(tree), x), right(tree))
    else:
        return make_node(value(tree), left(tree), add_node(right(tree), x) )

def make_binary_search_tree(a):
    tree = EmptyTree
    
    
    
    for num in a:
        tree = add_node(tree, num)
    return tree

def inorder(tree):
    if is_empty(tree):
        return []
    return inorder(left(tree)) + [value(tree)] + inorder(right(tree))

def preorder(tree):
    if is_empty(tree):
        return []
    return [value(tree)] + preorder(left(tree)) + preorder(right(tree))

def postorder(tree):
    if is_empty(tree):
        return []
    return postorder(left(tree)) + postorder(right(tree)) + [value(tree)]


def calc(tree):
    if is_empty(right(tree)) or is_empty(left(tree)):
        return value(tree)

    if value(tree) == "+":
        return calc(right(tree)) + calc(left(tree))
    elif value(tree) == "-":
        return calc(right(tree)) - calc(left(tree))
    elif value(tree) == "*":
        return calc(right(tree)) * calc(left(tree))
    elif value(tree) == "/":
        return calc(right(tree)) / calc(left(tree))

def recover(preorder, inorder):
    
    
    
    
    if len(inorder) == 0:
        return EmptyTree
    root_val = preorder[0]
    idx = inorder.index(root_val)
    left = inorder[:idx]
    right = inorder[idx+1:]
    return make_node(root_val, recover(preorder[1:], left),  recover(preorder[1+len(left):],right) )

n = input()
pre = list(map(int, input().split()))
ino = list(map(int, input().split()))
t = recover(pre, ino)
t = map(str, postorder(t))
print(' '.join(t))

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

post=[]
i = -1
def reconstruction(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)))