Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Reconstruction of a Tree

  Write a program which reads two sequences of nodes obtained by the preorder tree walk and the inorder tree walk on a binary tree respectively, and prints a sequence of the nodes obtained by the postorder tree walk on the binary tree.

Input

  In the first line, an integer $n$, which is the number of nodes in the binary tree, is given.

  In the second line, the sequence of node IDs obtained by the preorder tree walk is given separated by space characters.

    In the second line, the sequence of node IDs obtained by the inorder tree walk is given separated by space characters.

  Every node has a unique ID from $1$ to $n$. Note that the root does not always correspond to $1$.

Output

Print the sequence of node IDs obtained by the postorder tree walk in a line. Put a single space character between adjacent IDs.

Constraints

$1 \leq n \leq 40$

Sample Input 1

5
1 2 3 4 5
3 2 4 1 5

Sample Output 1

3 4 2 5 1

Sample Input 2

4
1 2 3 4
1 2 3 4

Sample Output 2

4 3 2 1



Sample input:
5
1 2 3 4 5
3 2 4 1 5


Sample output:
3 4 2 5 1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_D
# 難しい 解き方は図を参照
import sys
sys.setrecursionlimit(2**20)  # 再帰回数上限の向上 かなり多くしないとREになる


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:  # 指定区間が1ノード以下になったらおかしいので終了
        return
    root = pre_ls[root_pos]
    mid = in_ls.index(root)  # rootを持つ要素のidxを返す

    # 木の復元
    # 左部分木がある場合
    if mid != l:
        root_pos_left = root_pos+1  # preorderにおいては左部分木のroot_posは必ず現在の位置の隣になる
        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:  # rは一つ先を指定していることに注意すると気付ける
        root_pos_right = root_pos+1+mid-l  # 右部分木のrootは、左部分木がおわった直後にある
        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)

# # print(T)
# for i in range(N):
#     print(T[i+1].parent, T[i+1].left, T[i+1].right)
# post orderの作成
post_ls = []
post_parse(T, ROOT, post_ls)

print(*post_ls)

Submission status: Accepted

Solution code:
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]
	# print(leftin)
	rightin = inList[index + 1:]
	# print(rightin)
	num_left = len(leftin)
	num_right = len(rightin)
	if num_left != 0:
		leftpre = preList[1:1 + num_left]
		# print(leftpre)
		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:]
		# print(rightpre)
		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))

Submission status: Accepted

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


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, parent=-1, left=-1, right=-1):
        self.parent = parent
        self.left = left
        self.right = right
def postorder(ns,i, 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: # root의 왼쪽노드가 존재한다면 왼쪽으로 재귀
        ns[po[0]].left = po[1]
        ns[po[1]].parent = po[0]
        poio_node(ns,po[1:i+1],io[:i]) # po, io 안의 왼쪽 노드들로만 재귀
    if i!=len(io)-1: # root의 오른쪽 노드가 존재한다면 오른쪽으로 재귀
        ns[po[0]].right = po[i+1]
        ns[po[i+1]].parent = po[0]
        poio_node(ns, po[i+1:], io[i+1:]) # po, io 안의 오른쪽 노드들로만 재귀
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))   ##0~(n-1)로 변환
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))

Submission status: Accepted

Solution code:
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 = []  # type: ignore

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

Submission status: Accepted

Solution code:
pos = 0
postorder = []
def reconstruction(l, r):
    global pos
    global postorder
    if l >= r:
        return
    # print(pos)
    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)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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 = []

# reconstruct the origin
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)

# 親ノード、degreeを設定する
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
 
# nodeTypeを設定する
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"
 
# depthを設定する
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])
 
# heightを設定する
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 = []

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

# Inorder
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)
    
# Postorder
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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
    # preorderから次の値を取り出す
    x = preo.pop(0)
    for i in range(len(l)):
        if l[i] == x:
            # preorderの値と一致したら、そこから左右に分割
            rec(l[:i])
            rec(l[i+1:])
    posto.append(x)
    return

rec(ino)
print(*posto)

Submission status: Accepted

Solution code:

class Node:
    left = -1
    right = -1


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

    # inorder[first:end]の要素でpreorderの一番手前にあるものが、
    # 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)))

Submission status: Accepted

Solution code:
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



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

#print (l1)
#print (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 = list(filter(lambda a : a != -1,l3[j:]))
            t1 = []
            for v in range(j+1,n+1):
                if (l3[v] == -1 ):
                    break
                t1.append(v)
#            t2 = list(filter(lambda a : a != -1,l3[:j]))
            t2 = []
            for v in range(j-1,0,-1):
                if (l3[v] == -1 ):
                    break
                t2.append(v)
#            print (l1[i],i,j,t1,t2)
            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)


#make node
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])
#    print(a,b,c)

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

#print ("Preorder")
#print ('',' '.join(map(str,r1)))
#print ("Inorder")
#print ('',' '.join(map(str,r2)))
#print ("Postorder")
print (' '.join(map(str,r3)))

Submission status: Accepted

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

Submission status: Accepted

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