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):
n = int(input())
preorderList = [int(i) for i in input().split()]
inorderList = [int(i) for i in input().split()]

class Node:
    def __init__(self, idn):
        self.id = idn
        self.left = -1
        self.right = -1
T = [Node(i+1) for i in range(n)]

def splitTree(P, I):
    b = I.index(P[0])
    if P[0] != I[0]:
        T[P[0]-1].left = P[1]
    if P[0] != I[-1]:
        T[P[0]-1].right = P[b+1]
    if b > 1:
        splitTree(P[1:b+1], I[:b])
    if b < len(I)-2:
        splitTree(P[b+1:], I[b+1:])

splitTree(preorderList, inorderList)
root = preorderList[0]

postorderList = []
def setPostorderList(p):
    if T[p-1].left != -1:
        setPostorderList(T[p-1].left)
    if T[p-1].right != -1:
        setPostorderList(T[p-1].right)
    postorderList.append(T[p-1].id)

setPostorderList(root)
print(*postorderList)

Solution (Python):
def reconstruction(l, r, p):
    if l >= r:
        return
    c = next(pre)
    m = ino.index(c)
    reconstruction(l, m, p)
    reconstruction(m + 1, r, p)
    p += [c]
n = int(input())
pre = iter(list(map(int, input().split())))
ino = list(map(int, input().split()))
postorder = []
reconstruction(0, n, postorder)
print(' '.join(map(str, postorder)))

Solution (Python):
n = int(input())
*preorder, = map(int, input().split())
*inorder, = map(int, input().split())


def reconstruction(l, r):
    global preorder
    global inorder

    if l >= r:
        return ""
    a = ""
    c = preorder.pop(0)
    i = inorder.index(c)
    a += reconstruction(l, i)
    a += reconstruction(i+1, r)
    a += f"{c} "
    return a


print(reconstruction(0, n).strip())

Solution (Python):
def reconstruct(pre_tree,in_tree):
    if not pre_tree:
        return -1
    root = pre_tree[0]
    idx = in_tree.index(root)
    tree[root] = (
        reconstruct(pre_tree[1:idx+1],in_tree[:idx]),
        reconstruct(pre_tree[idx+1:],in_tree[idx+1:])
    )
    return root

def post_walk(idx):
    if idx == -1:
        return 
    l_idx,r_idx = tree[idx]
    yield from post_walk(l_idx)
    yield from post_walk(r_idx)
    yield idx

n = int(input())
tree = [None]*(n+1)
pre_lst = list(map(int,input().split()))
in_lst = list(map(int,input().split()))

reconstruct(pre_lst,in_lst)
print(' '.join(map(str,post_walk(pre_lst[0]))))

Solution (Python):

import queue

class Node:
    def __init__(self, myNum, left, right):
        self.myNum = myNum
        self.left = left
        self.right = right
        self.parent = -1
        self.bs = -1
        self.nodeType = ""
        self.degree = -1
        self.depth = -1
        self.height = -1


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


def createTree(preorder, inorder):
    if not preorder:
        return -1
    if not inorder:
        return -1
    parent = preorder[0]
    pidx = inorder.index(parent)
    leftInorder = inorder[:pidx]
    rightInorder = inorder[pidx+1:]
    leftPreorder = []
    rightPreorder = []
    for item in preorder:
        if item in leftInorder:
            leftPreorder.append(item)
        if item in rightInorder:
            rightPreorder.append(item)
    left = createTree(leftPreorder,leftInorder)
    right = createTree(rightPreorder,rightInorder)
    nodes.append(Node(parent, left, right))
    return parent

createTree(preorder, inorder)
nodes = sorted(nodes, key = lambda x: x.myNum)


for node in nodes:
    dg = 0
    if node.left != -1:
        nodes[node.left].parent = node.myNum
        dg += 1
    if node.right != -1:
        nodes[node.right].parent = node.myNum
        dg += 1
    node.degree = dg
 

for node in nodes:
    if node.left != -1 and node.right != -1:
        nodes[node.left].bs = nodes[node.right].myNum
        nodes[node.right].bs = nodes[node.left].myNum
 

for node in nodes:
    if node.parent == -1:
        node.nodeType = "root"
        node.depth = 0
        rootNum = node.myNum
    elif node.left == -1 and node.right == -1:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"
 

q = queue.Queue()
q.put(nodes[rootNum])
while not q.empty():
    nd = q.get()
    if nd.left != -1:
        nodes[nd.left].depth = nd.depth + 1
        q.put(nodes[nd.left])
    if nd.right != -1:
        nodes[nd.right].depth = nd.depth + 1
        q.put(nodes[nd.right])
 

for node in nodes:
    if node.parent == -1 or node.nodeType == "leaf":
        node.height = 0
        q.put(node)
while not q.empty():
    nd = q.get()
    if nd.parent != -1:
        nodes[nd.parent].height = max(nodes[nd.parent].height, nd.height + 1)
        q.put(nodes[nd.parent])

ans = []


def dfsPreorder(x):
    if nodes[x].height == 0:
        ans.append(x)
        return
    
    ans.append(nodes[x].myNum)
    if nodes[x].left != -1:
        dfsPreorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPreorder(nodes[x].right)


def dfsInorder(x):
    if nodes[x].height == 0:
        ans.append(x)
        return
    
    if nodes[x].left != -1:
        dfsInorder(nodes[x].left)
    ans.append(nodes[x].myNum)
    if nodes[x].right != -1:
        dfsInorder(nodes[x].right)
    

def dfsPostorder(x):
    if nodes[x].height == 0:
        ans.append(x+1)
        return
    
    if nodes[x].left != -1:
        dfsPostorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPostorder(nodes[x].right)
    ans.append(nodes[x].myNum+1)

dfsPostorder(rootNum)
print(" ".join(str(i) for i in ans))

Solution (Python):
from sys import stdin

class Node:
    def __init__(self):
        self.children = [-1, -1]



def initNode(t_pre, t_in):
    global nodes
    if len(t_in) == 1:
        nodes[t_in[0]].children = [-1, -1]
        return t_in[0]
    else:
        r = t_in.index(t_pre[0])
        if r == 0: 
            rr = initNode(t_pre[1:], t_in[1:])
            nodes[t_in[r]].children = [-1, rr]
        elif r == len(t_in)-1: 
            lr = initNode(t_pre[1:r+1], t_in[:r])
            nodes[t_in[r]].children = [lr, -1]
        else:
            lr = initNode(t_pre[1:r+1], t_in[:r])
            rr = initNode(t_pre[r+1:], t_in[r+1:])
            nodes[t_in[r]].children = [lr, rr]

        return t_in[r]

def postorder(i):
    global nodes, res
    if i != -1:
        c = nodes[i].children
        postorder(c[0])
        postorder(c[1])
        res.append(i)

n = int(stdin.readline().rstrip())
t_pre = [int(x) for x in stdin.readline().rstrip().split()]
t_in = [int(x) for x in stdin.readline().rstrip().split()]

nodes = [Node() for _ in range(n+1)]
initNode(t_pre, t_in)

res = []
postorder(t_pre[0])
print(*res)

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
preo = LIST()
ino = LIST()
posto = []

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

rec(ino)
print(*posto)

Solution (Python):

class Node:
    left = -1
    right = -1


def get_root_index(first: int, end: int) -> int:
    """inorder[first:end]の根のインデックスを取得する。
    根： inorder[first:end]を左部分木と右部分木に分割するノード
    """

    
    
    
    for pre in preorder:
        for j in range(first, end):
            if pre == inorder[j]:
                return j


def get_root(first, end) -> int:
    """inorder[first:end]の根のノードを返す。
    """

    root_ix = get_root_index(first, end)
    if root_ix is not None:
        return inorder[root_ix]
    else:
        return -1


def set_nodes(first: int, end: int):
    root_ix = get_root_index(first, end)
    if first + 1 < root_ix:
        set_nodes(first, root_ix)
    if root_ix + 1 < end - 1:
        set_nodes(root_ix + 1, end)
    nodes[inorder[root_ix]].left = get_root(first, root_ix)
    nodes[inorder[root_ix]].right = get_root(root_ix + 1, end)


def set_postorder(node_id: int) -> None:
    """後行順巡回で得られる節の番号を保存する。

    Args:
        node_id (int): [description]
    """

    left = nodes[node_id].left
    if left != -1:
        set_postorder(left)

    right = nodes[node_id].right
    if right != -1:
        set_postorder(right)

    postorder.append(node_id)


N = int(input())
nodes = [Node() for i in range(N + 1)]
preorder = [int(i) for i in input().split()]
inorder = [int(i) for i in input().split()]

set_nodes(0, N)

postorder = []
set_postorder(get_root(0, N))
print(' '.join(map(str, postorder)))

Solution (Python):
import copy
class node:
    def __init__(self,nodeid):
        self.parent = None
        self.parentid = -1
        self.c_leftid = -1
        self.c_left = None
        self.c_rightid = -1
        self.c_right = None
        self.nodeid = nodeid
        self.type = "root"
    def setLeftChild(self,cn):
        self.c_left = cn
        self.c_leftid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def setRightChild(self,cn):
        self.c_right = cn
        self.c_rightid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 ):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt
    def setNodeType(self):
        if (self.getDepth() == 0):
            self.type = "root"
        else:
            if ( self.c_rightid == -1 and self.c_leftid == -1 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def getSibling(self):
        if ( self.parentid == -1):
            return -1
        i = self.parent
        if ( i.c_rightid == self.nodeid ):
            return i.c_leftid
        elif ( i.c_leftid == self.nodeid):
            return i.c_rightid
    def getHeight(self):
        lcnt = 0
        rcnt = 0
        if (self.c_leftid == -1  and self.c_rightid == -1 ):
            return 0
        elif (self.c_rightid  == -1):
            lcnt = lcnt + self.c_left.getHeight() + 1
        elif (self.c_leftid  == -1):
            rcnt = rcnt + self.c_right.getHeight() + 1
        else:
            lcnt = lcnt + self.c_left.getHeight() + 1
            rcnt = rcnt + self.c_right.getHeight() + 1
        if (lcnt >= rcnt):
            return lcnt
        else:
            return rcnt
    def getDegree(self):
        cnt = 0
        if (self.c_leftid != -1):
            cnt += 1
        if (self.c_rightid != -1):
            cnt += 1
        return cnt
    def getPreorder(self,r1):
        r1.append(self.nodeid)
        if (self.c_leftid != -1):
            r1 = self.c_left.getPreorder(r1)
        if (self.c_rightid != -1):
            r1 = self.c_right.getPreorder(r1)
        return r1       
    def getInorder(self,r1):
        if (self.c_leftid != -1):
            r1 = self.c_left.getInorder(r1)
        r1.append(self.nodeid)
        if (self.c_rightid != -1):
            r1 = self.c_right.getInorder(r1)
        return r1       
    def getPostorder(self,r1):
        if (self.c_leftid != -1):
            r1 = self.c_left.getPostorder(r1)
        if (self.c_rightid != -1):
            r1 = self.c_right.getPostorder(r1)
        r1.append(self.nodeid)
        return r1       
    def getRoot(self):
        if (self.parentid == -1):
            return self
        return self.parent.getRoot()


    def showNode(self):
        i1 = self.nodeid
        i2 = self.parentid
        i3 = self.getSibling()
        i4 = self.getDegree()
        i5 = self.getDepth()
        i6 = self.getHeight()
        i7 = self.getNodeType()
        print ('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i1,i2,i3,i4,i5,i6,i7))
        return




n = int(input())
l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))
l1.insert(0,-1)
l1.append(-1)
l2.insert(0,-1)
l2.append(-1)
l3 = copy.deepcopy(l2)




ilist = []
for i in range(1,n+1):
    tmp = []
    for j in range(1,n+1):
        if (l1[i] == l2[j]):
            l3[j] = -1

            t1 = []
            for v in range(j+1,n+1):
                if (l3[v] == -1 ):
                    break
                t1.append(v)

            t2 = []
            for v in range(j-1,0,-1):
                if (l3[v] == -1 ):
                    break
                t2.append(v)

            tmp.append(l1[i])
            if (len(t2) > 0):
                tmp.append(l1[i+1])
                for k in range(1,n + 1):
                    if (l3[k] == l1[i+1]):
                        l3[k] = -1
            else:
                tmp.append(-1)
            if (len(t1) > 0):
                tmp.append(l1[i+len(t2)+1])
                for k in range(1,n + 1):
                    if (l3[k] == l1[i+len(t2)+1]):
                        l3[k] = -1
            else:
                tmp.append(-1)
            ilist.append(tmp)



nl = []
for i in range(0,n+1):
    nl.append(node(i))

for t in ilist:
    (a,b,c) = map(int,t)
    if (b != -1):
        nl[a].setLeftChild(nl[b])
    if (c != -1):
        nl[a].setRightChild(nl[c])


root = nl[1].getRoot()
r1 = []
r2 = []
r3 = []
r1 = root.getPreorder(r1)
r2 = root.getInorder(r2)
r3 = root.getPostorder(r3)






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

Solution (Python):
def reconstruct(preorder, inorder, postorder):
    if len(preorder) == 0:
        return
    node_no = preorder[0]
    node_div = inorder.index(node_no)

    reconstruct(preorder[1:node_div+1], inorder[:node_div], postorder)
    reconstruct(preorder[node_div+1:], inorder[node_div+1:], postorder)

    postorder.append(node_no)
    return

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

    postorder = []
    reconstruct(preorder, inorder, postorder)
    print(" ".join(map(str, postorder)))

main()

Solution (Python):
import sys

def flatten(data):
    for item in data:
        if hasattr(item, '__iter__'):
            for element in flatten(item):
                yield element
        else:
            yield item

n = int(sys.stdin.readline())
preorder = list(map(int, sys.stdin.readline().split()))
inorder = list(map(int, sys.stdin.readline().split()))

def eq(a, b):
    if type(a)!=type(b):  return False   
    if type(a)==list:     return set(flatten(a))== set(flatten(b)) 
    return a==b   

while len(preorder)>1:
    for i in range(len(preorder)-3,-2,-1):
        seq = preorder[i:i+3]
        for j in range(len(inorder)-3,-2,-1):
            if type(preorder[i+1])==int:
                if eq(preorder[i+1], inorder[j+1]) and eq(preorder[i+2], inorder[j+2]):
                    
                    preorder[i+1:i+3] = [[preorder[i+1], 0, preorder[i+2]]]
                    inorder[j+1:j+3]  = [[0, inorder[j+1], inorder[j+2]]]
                    break
                if eq(preorder[i+1], inorder[j+2]) and eq(preorder[i+2], inorder[j+1]):
                    
                    preorder[i+1:i+3] = [[preorder[i+1], preorder[i+2], 0]]
                    inorder[j+1:j+3]  = [[inorder[j+1], inorder[j+2], 0]]
                    break
            if i>=0 and j>=0 and type(preorder[i])==int and eq(preorder[i], inorder[j+1]) and eq(preorder[i+1], inorder[j]) and  eq(preorder[i+2], inorder[j+2]): 
                preorder[i:i+3]=[seq]
                inorder[j:j+3]=[inorder[j:j+3]]
                break
        else:  continue
        break


postorder=[]
def create_postorder(a):
    if type(a)==list:
        for i in [1, 2, 0]: 
            if type(a[i])==list:  create_postorder(a[i])
            elif a[i]>0:          postorder.append(a[i])
    else:  postorder.append(a)
create_postorder(preorder[0])
print(' '.join(map(str, postorder)))

Solution (Python):


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



def mk_tree(Tree,p_order,in_order):
    tmp_p_order=[]
    tmp_in_order=[]
    root=p_order[0]

    root_ind=0    
    while(in_order[root_ind] != root):
        root_ind+=1



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

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


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






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

mk_tree(Tree,p_order,in_order)


 



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

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


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

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

Solution (Python):
pos = 0

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


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


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

solve(pre_order, in_order)

Solution (Python):

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

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

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

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

n = int(input())
nds = [Node(i+1) for i in range(n)] 
preo = [nds[int(i)-1] for i in input().split()]
ino = [nds[int(i)-1] for i in input().split()]

root = rec(preo, ino)
from collections import deque
dq = deque()

visited = [None]*n
cnt = 0
dq.append(root)
while len(dq) > 0:
    pp = dq.pop()
    dl = pp.num_child()
    if dl == 0:
        visited[cnt] = pp
        cnt += 1
        continue
    if dl > 0:
        l,r = pp.left, pp.right
        if (l and l not in visited) or (r and r not in visited):
            if pp: dq.append(pp)
            if r: dq.append(r)
            if l: dq.append(l)
        else:
            visited[cnt] = pp
            cnt += 1
            continue

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