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:
#!/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


# recursively defines a binary tree
# node.left or node.right may also be a binary tree
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)

Submission status: Accepted

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

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

output:
3 4 2 5 1
"""

import sys


# recursively defines a binary tree
# node.left or node.right may also be a binary tree
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)

        # append rt.val at last to implement post_order node scan
        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()))
    # assert len(pre_order) == len(in_order) == array_length
    
    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()

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# ????????¢?´¢??¨??¨??????????????????tree???x?????????????????°????????¨?????????
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
    # ????????????????????¶:
    # ????????????i???????????£?????¨????????¨????¬????????????????????????§??????
    # a?????????i???????????§???????´????????????¢?´¢??¨tree????????????????????????
    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):
    # preorder??????????????????root
    # root???inorder??????????????¢???
    # inorder??????root????¢??????????
    # ?????????????????????Node??????????????£???????????????????????£?????????
    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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding=utf-8
def reconstruction(left, right):
    global pre_order
    global in_order
    global post_order
    global n

    if left > right:
        return None
    elif left == right:
        root = pre_order.pop(0)
        post_order.append(root)
        return None
    else:
        root = pre_order.pop(0)

    root_pos = in_order.index(root)
    reconstruction(left, root_pos-1)
    reconstruction(root_pos+1, right)
    post_order.append(root)

n = int(input())
pre_order = list(map(int, input().split()))
in_order = list(map(int, input().split()))
post_order = []

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

Submission status: Accepted

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


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

Submission status: Accepted

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

def getidx(Tree,value):
    idx = -1
    for i in range(len(Tree)):
        if Tree[i][I] == value:
            idx = i
            break
    return idx

def search(Tree, A, B, num):
    root = A[0]
    rootidx = getidx(Tree,root)
    ld = num
    for i in range(num):
        if B[i] == root:
            ld = i
            break
    if ld > 0:
        left,lidx = search(Tree,A[1:ld+1],B[:ld],ld)
        Tree[rootidx][L] = lidx
    rt = ld + 1
    if rt < num:
        right,ridx = search(Tree,A[rt:],B[rt:],num - rt)
        Tree[rootidx][R] = ridx
    return (root,rootidx)

def postorder(Tree, nidx, A):
    if nidx < 0:
        return
    postorder(Tree,Tree[nidx][L],A)
    postorder(Tree,Tree[nidx][R],A)
    A.append(Tree[nidx][I])


def main():

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

    root,ridx = search(tree, plist, ilist, num)

    pos = []

    postorder(tree, ridx, pos)
    print(" ".join(map(str,pos)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    return result


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

    print(*get_postorder(preorder, inorder))

Submission status: Accepted

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

Solution code:
n = int(input())
tree = [None for i in range(n +1)]
list_pre = list(map(int, input().split()))
list_in = list(map(int, input().split()))
 
 
def solve(tree_pre, tree_in):
    if not tree_pre:
        return -1
    root = tree_pre[0]
    idx = tree_in.index(root)
    tree[root] = (solve(tree_pre[1:idx + 1], tree_in[:idx]), 
                  solve(tree_pre[idx + 1:],  tree_in[idx + 1:]))
    return root


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


solve(list_pre, list_in)

print(*post_order_search(list_pre[0]))

Submission status: Accepted

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


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

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

    return root


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


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

Submission status: Accepted

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


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

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

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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
import sys
sys.setrecursionlimit(100000)


if __name__ == '__main__':

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Node:

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

class BTree:

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

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

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

            return root

        else:
            return -1

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

if __name__ == '__main__':

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

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

    btree.make_tree(preorder, inorder)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
j,a=0,[]
def f(l,r):
 if l<r:
  global j,a;c=p[j];j+=1;m=i.index(c)
  f(l,m);f(m+1,r);a+=[c]
n,p,i=int(input()),input().split(),input().split()
f(0,n);print(*a)

Submission status: Accepted

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(*postorder(pre_tree[0]))

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


if __name__ == '__main__':
    run()

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):
    p = po[0]
    i = io.index(p)
    if i != 0:
        ns[p].left = po[1]
        ns[po[1]].parent = p
        poio_node(ns, po[1:i + 1], io[:i])
    if i != len(io) -1:
        ns[p].right = po[i + 1]
        ns[po[1 + i]].parent = p
        poio_node(ns, po[i + 1:], io[i + 1:])

def min1(n):
    return n - 1
    
n = int(input())
po = list(map(int, input().split()))
io = list(map(int, input().split()))
po = list(map(min1, po))
io = list(map(min1, io))
ns = [Node() for i in range(n)]

poio_node(ns, po, io)

post = []
postorder(ns, po[0], post)
print(" ".join(post))

Submission status: Accepted

Solution code:
from collections import deque


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


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


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

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

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

    post_lst.append(c)
    return


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

solve()

Submission status: Accepted

Solution code:
INF = 10**3


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

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

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


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

Submission status: Accepted

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

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


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

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

Submission status: Accepted

Solution code:
#coding:utf-8
N = int(input())
preList = list(input().split())
inList = list(input().split())

def recon(l,r):
    if l >= r:
        return
    global pos
    c = preList[pos]
    index = inList.index(c)
    pos += 1
    recon(l,index)
    recon(index+1,r)
    
    global answer
    answer.append(c)

answer = []
pos = 0
recon(0,N)

answer = " ".join(answer)
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

Reconstruction(0, n)
print(*C)

Submission status: Accepted

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

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

pos = 0
post_ls = []

def rec(left: int, right: int):
    global pos
    if left >= right:
        return
    tmp_root = pre_ls[pos]
    pos += 1
    mid = in_ls.index(tmp_root)
    # 右部分木->左部分木->根の後方順巡回になっている
    rec(left, mid)
    rec(mid+1, right)
    post_ls.append(tmp_root)


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

pos = 0

def rec(l, r,):
    global pos # posはglobal変数だと明示する
    if l >= r:
        return
    root = pre[pos]
    pos += 1
    m = ino.index(root)
    rec(l, m)
    rec(m+1, r)
    post.append(str(root))

pos = 0

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

Submission status: Accepted

Solution code:


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

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