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: Wrong Answer

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


root = pre[1]
pre = iter(pre).__next__

def dfs(l, r):
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    print(c)
    
dfs(0, len(ino))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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:
                left_preorder.append(preorder[i])
                if len(left_preorder) == len(left_inorder):
                    flag = True
            else:
                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)

Submission status: Wrong Answer

Solution code:
I = 0
L = 1
R = 2
P = 3
B = 4
D = 5
H = 6

def search(N, A, B, num):
    root = A[0]
    ld = num
    for i in range(num):
        if B[i] == root:
            ld = i
            break
    if ld > 0:
        N[root][L] = search(N,A[1:ld+1],B[:ld],ld)
    rt = ld + 1
    if rt < num:
        N[root][R] = search(N,A[rt:],B[rt:],num - rt)
    return root

def postorder(N,id,A):
    if id < 0:
        return
    postorder(N,N[id][L],A)
    postorder(N,N[id][R],A)
    A.append(id)


def main():

    """ ????????? """
    num = int(input().strip())
    plist = list(map(int,input().split()))
    ilist = list(map(int,input().split()))
    pos = []
    
    nodes = [[i, -1, -1, -1, -1, 0, 0] for i in range(num)]

    search(nodes,plist,ilist,num)
    pos = []

    print(" ".join(map(str,pos)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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()))
inotree = list(map(int, input().split()))
root = pretree[0]
root_index = inotree.index(root)
SET = set(pretree) - {root}
ans = []
def treeSet(A, i):
    if len(A) == 0:
        return
    global SET
    c = root
    r = pretree.index(A[0])
    for a in pretree[i: r + 1]:
        if c != a:
            SET -= {a}
            tree[c].setc(a)
            c = a
    for b in A[1:]:
        if b not in SET:
            c = b
            continue
        SET.add(b)
        tree[c].setc(b)
        c = b
treeSet(inotree[:root_index], 0)
treeSet(inotree[root_index + 1:], root_index + 1)
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)

Submission status: Wrong Answer

Solution code:
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(tree)
print(*postorder(pre_tree[0]))

Submission status: Wrong Answer

Solution code:
INF = 10**3


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

    c = INF
    for i in i_ary[l:r]:
        ind = p_ary.index(i)
        if ind < c:
            c = i
    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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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): #generate_left_tree
    global p
    p += 1
    tmp = p
    i = iol.index(pol[p])
    gen_tree(pol[p])
    node_dic[root].left = pol[tmp]

def grt(root): #generate_right_tree
    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()) #pre_order_list
iol = map(int, raw_input().split()) #in_order_list
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])
        #print left_preorder,left_inorder
        #print right_preorder,right_inorder
        #print
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:UTF-8

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

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D

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):
    #print(preorder_list, inorder_list)
    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()

Submission status: Accepted

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

"""
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):
    # write your code here
    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()))
    # assert len(pre_order) == len(in_order) == array_length

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