Problem:


Tree Walk

Binary trees are defined recursively. A binary tree T is a structure defined on a finite set of nodes that either

contains no nodes, or

is composed of three disjoint sets of nodes:

- a root node.

- a binary tree called its left subtree.

- a binary tree called its right subtree.

Your task is to write a program which perform tree walks (systematically traverse all nodes in a tree) based on the following algorithms:

Print the root, the left subtree and right subtree (preorder).

Print the left subtree, the root and right subtree (inorder).

Print the left subtree, right subtree and the root (postorder).

Here, the given binary tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n linen, the information of each node is given in the following format:

id left right

id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left(right) is indicated by -1

Output

In the 1st line, print "Preorder", and in the 2nd line print a list of node IDs obtained by the preorder tree walk.

In the 3rd line, print "Inorder", and in the 4th line print a list of node IDs obtained by the inorder tree walk.

In the 5th line, print "Postorder", and in the 6th line print a list of node IDs obtained by the postorder tree walk.

Print a space character before each node ID.

Constraints

1 ≤ n ≤ 25

Sample Input 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

Sample Output 1

Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1


Sample output:
Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

Submission status: Accepted

Solution code:
# Tree walk

import sys
sys.setrecursionlimit(10**9)  # 再帰回数上限の向上 かなり多くしないとREになる

class Node:
    def __init__(self, parent, left, right):
        self.parent = parent #  親
        self.left = left # 左の子ノード
        self.right = right # 右の子ノード

def pre_parse(T: dict, u: int, pre_ls: list):
    # 深さ優先探索特有の即時終了条件
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  # より左の方から深さ優先探索
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    # 左→中→右っていうちょっと気持ち悪い順番
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


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())
T = {key: Node(None, None, None) for key in range(n)}
for _ in range(n):
    tmp = [x if x != -1 else None for x in map(int, input().split())]
    T[tmp[0]].left = tmp[1]
    T[tmp[0]].right = tmp[2]
    if tmp[1] is not None:
        T[tmp[1]].parent = tmp[0]
    if tmp[2] is not None:
        T[tmp[2]].parent = tmp[0]

# parentがないのが特徴のROOTを探す
for id, node in T.items():
    if node.parent is None:
        ROOT = id

# リストに答えを格納していく
pre_ls, in_ls, post_ls = [], [], []
pre_parse(T, ROOT, pre_ls)
in_parse(T, ROOT, in_ls)
post_parse(T, ROOT, post_ls)

print('Preorder')
print('', *pre_ls)
print('Inorder')
print('', *in_ls)
print('Postorder')
print('', *post_ls)

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())
prt = [-1 for i in range(n)]
chd = [[] for i in range(n)]
root = -1

def preOrder(num):
    if num == -1:
        return
    print(f' {num}', end = '')
    preOrder(chd[num][0])
    preOrder(chd[num][1])

def inOrder(num):
    if num == -1:
        return
    inOrder(chd[num][0])
    print(f' {num}', end = '')
    inOrder(chd[num][1])

def postOrder(num):
    if num == -1:
        return
    postOrder(chd[num][0])
    postOrder(chd[num][1])
    print(f' {num}', end = '')
    
for i in range(n):
    idx, left, right = map(int, input().split())
    chd[idx].append(left)
    chd[idx].append(right)
    if left >= 0:
        prt[left] = idx
    if right >= 0:
        prt[right] = idx

for i in range(n):
    if prt[i] == -1:
        root = i
        break

print('Preorder')
preOrder(root)
print('\nInorder')
inOrder(root)
print('\nPostorder')
postOrder(root)
print('')

Submission status: Accepted

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

pre = []
def preorder(t, n):
    pre.append(n)
    if t[n].left is not None:
        preorder(t, t[n].left)
    if t[n].right is not None:
        preorder(t, t[n].right)

ino = []
def inorder(t, n):
    if t[n].left is not None:
        inorder(t, t[n].left)
        ino.append(n)
    else:
        ino.append(n)
    if t[n].right is not None:
        inorder(t, t[n].right)
    if n not in ino:
        ino.append(n)

post = []
def postorder(t, n):
    if t[n].left is not None:
        postorder(t, t[n].left)
    if t[n].right is not None:
        postorder(t, t[n].right)
    post.append(n)

n = int(input())
t = {k: Node(None, None, None) for k in range(n)}
for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] != -1:
        t[tmp[1]].parent = tmp[0] # 親
        t[tmp[0]].left = tmp[1] # 左の子
    if tmp[2] != -1:
        t[tmp[2]].parent = tmp[0] # 親
        t[tmp[0]].right = tmp[2] # 右の子

for node in range(n):
    if t[node].parent is None:
        preorder(t, node)
        inorder(t, node)
        postorder(t, node)

print("Preorder")
print(" " + " ".join([str(k) for k in pre]))
print("Inorder")
print(" " + " ".join([str(k) for k in ino]))
print("Postorder")
print(" " + " ".join([str(k) for k in post]))

Submission status: Accepted

Solution code:
class TreeNode:
    def __init__(self):
        self.val=-1
        self.left=-1
        self.right=-1
        self.parent=-1

n=int(input())
nodes=[TreeNode() for _ in range(n)]

for _ in range(n):
    idx,left,right=map(int,input().split())
    nodes[idx].val=idx
    nodes[idx].left=left
    nodes[idx].right=right
    if(left!=-1):
        nodes[left].parent=idx
    if(right!=-1):
        nodes[right].parent=idx

root_idx=-1
for i in range(n):
    if(nodes[i].parent==-1):
        root_idx=i
        break

preorder_idx=[]
def preOrder(idx):
    preorder_idx.append(idx)
    if(nodes[idx].left!=-1):
        preOrder(nodes[idx].left)
    if(nodes[idx].right!=-1):
        preOrder(nodes[idx].right)

inorder_idx=[]
def inOrder(idx):
    if(nodes[idx].left!=-1):
        inOrder(nodes[idx].left)
    inorder_idx.append(idx)
    if(nodes[idx].right!=-1):
        inOrder(nodes[idx].right)

postorder_idx=[]
def postOrder(idx):
    if(nodes[idx].left!=-1):
        postOrder(nodes[idx].left)
    if(nodes[idx].right!=-1):
        postOrder(nodes[idx].right)
    postorder_idx.append(idx)


preOrder(root_idx)
inOrder(root_idx)
postOrder(root_idx)

print("Preorder")
print(" ",end="")
print(*preorder_idx)

print("Inorder")
print(" ",end="")
print(*inorder_idx)

print("Postorder")
print(" ",end="")
print(*postorder_idx)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, id):
        self.id = id
        self.left = -1
        self.right = -1
def walk_preorder(node, order_list):
    if node == None:
        return 0
    order_list.append(node.id)
    walk_preorder(nodes.get(node.left), order_list)
    walk_preorder(nodes.get(node.right), order_list)
def walk_inorder(node, order_list):
    if node == None:
        return 0
    walk_inorder(nodes.get(node.left), order_list)
    order_list.append(node.id)
    walk_inorder(nodes.get(node.right), order_list)
def walk_postorder(node, order_list):
    if node == None:
        return 0
    walk_postorder(nodes.get(node.left), order_list)
    walk_postorder(nodes.get(node.right), order_list)
    order_list.append(node.id)

n = int(input())
nodes = {}
for _ in range(n):
    id, left, right = [int(x) for x in input().split(' ')]
    node = Node(id)
    node.left = left
    node.right = right
    nodes[id] = node
is_child_table = {node_id:False for node_id in range(n)}
for id in nodes:
    if nodes[id].left > -1:
        is_child_table[nodes[id].left] = True
    if nodes[id].right > -1:
        is_child_table[nodes[id].right] = True
root_id = [node_id for node_id in is_child_table.keys() if is_child_table[node_id] == False][0]
root_node = nodes[root_id]

preorder_list = []
inorder_list = []
postorder_list = []
walk_preorder(root_node, preorder_list)
walk_inorder(root_node, inorder_list)
walk_postorder(root_node, postorder_list)
print('Preorder')
preorder_str = ' '.join(map(str, preorder_list))
print(' {}'.format(preorder_str))
print('Inorder')
inorder_str = ' '.join(map(str, inorder_list))
print(' {}'.format(inorder_str))
print('Postorder')
postorder_str = ' '.join(map(str, postorder_list))
print(' {}'.format(postorder_str))

Submission status: Accepted

Solution code:
class Tree:
  def __init__(self):
    self.parent = -1
    self.brother = -1
    self.lchild = -1
    self.rchild = -1

n = int(input())

A = [Tree() for _ in range(n)]

for i in range(n):
  id, *children = [int(x) for x in input().split()]
  A[id].lchild, A[id].rchild = children
  if A[id].lchild != -1 and A[id].rchild != -1:
    A[A[id].lchild].brother = A[id].rchild
  for child in children:
    if child != -1:
      A[child].parent = id

root = [i for i, x in enumerate(A) if x.parent == -1][0]

def preorder(A,C,a):
  C.append(a)
  F = []
  if A[a].lchild != -1:
    preorder(A,C,A[a].lchild)
    if A[a].rchild != -1:
      F.append(A[a].rchild)
  elif A[a].rchild != -1:
    preorder(A,C,A[a].rchild)
  elif A[a].brother != -1:
    preorder(A,C,A[a].brother)
  while F != []:
    f = F.pop()
    if not f in C:
      preorder(A,C,f)
  return C

def start(A,a):
  global b
  b = A[a].lchild
  if b != -1:
    start(A,b)
  else:
    b = a
  return b

def inorder(A,D,a):
  if A[a].lchild == -1:
    D.append(a)
    if A[a].rchild != -1:
      inorder(A,D,start(A,A[a].rchild))
  if A[a].parent != -1:
    c = A[a].parent
    if a == A[c].lchild and A[c].rchild != -1:
      D.append(c)
      inorder(A,D,start(A,A[c].rchild))
    elif a == A[c].lchild and A[c].rchild == -1:
      D.append(c)
      inorder(A,D,c)
    elif a == A[c].rchild and A[c].lchild != -1:
      inorder(A,D,c)

def postorder(A,E,a,e):
  if A[a].lchild == -1 and A[a].rchild != -1:
    postorder(A,E,start(A,A[a].rchild),A[a].rchild)
  E.append(a)
  if a != e:
    if A[a].brother != -1:
      postorder(A,E,start(A,A[a].brother),e)
    else:
      postorder(A,E,A[a].parent,e)

C = []
D = []
E = []

print("Preorder")
print(" ",end="")
print(" ".join(map(str, preorder(A,C,root))))
print("Inorder")
print(" ",end="")
s = start(A,root)
inorder(A,D,s)
print(" ".join(map(str, D)))
print("Postorder")
print(" ",end="")
postorder(A,E,s,root)
print(" ".join(map(str, E)))

Submission status: Accepted

Solution code:
def preOrder(s):
	print(" " + str(s),end="")
	if main[s][1] != -1:
		preOrder(main[s][1])
	if main[s][2] != -1:
		preOrder(main[s][2])

def inOrder(s):
	if main[s][1] != -1:
		inOrder(main[s][1])
	print(" " + str(s),end="")
	if main[s][2] != -1:
		inOrder(main[s][2])

def postOrder(s):
	if main[s][1] != -1:
		postOrder(main[s][1])
	if main[s][2] != -1:
		postOrder(main[s][2])
	print(" " + str(s),end="")

n = int(input())
main = [[-1] * 1 for i in range(n+1)]
for i in range(n):
	a = input().split()
	for j in range(1,3):
		main[int(a[j])][0] = int(a[0])
		main[int(a[0])].append(int(a[j]))
	#print(main)

del a


for i in range(n):
	if main[i][0] == -1:
		print("Preorder")
		preOrder(int(i))
		print()
		print("Inorder")
		inOrder(int(i))
		print()
		print("Postorder")
		postOrder(int(i))
		break
print()

#print(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 get_degree(self):
        d = 0
        if self.left != -1:
            d += 1
        if self.right != -1:
            d += 1
        return d

class BinaryTree:
    
    def __init__(self, size):
        self.tree = [Node() for i in range(N)]
    
    def set(self, node_id, left, right):
        self.tree[node_id].left = left
        self.tree[node_id].right = right

        if left != -1:
            self.tree[left].parent = node_id
        if right != -1:
            self.tree[right].parent = node_id
    
    def get_root(self):
        for i in range(len(self.tree)):
            node = self.tree[i]
            if node.parent == -1:
                return i
    
    def walk_preorder(self, node):
        if node == -1:
            return
        print(' %d' % (node), end = '')
        self.walk_preorder(self.tree[node].left)
        self.walk_preorder(self.tree[node].right)
    
    def walk_inorder(self, node):
        if node == -1:
            return
        self.walk_inorder(self.tree[node].left)
        print(' %d' % (node), end = '')
        self.walk_inorder(self.tree[node].right)
    
    def walk_postorder(self, node):
        if node == -1:
            return
        self.walk_postorder(self.tree[node].left)
        self.walk_postorder(self.tree[node].right)
        print(' %d' % (node), end = '')

N = int(input())

# 二分木初期化
binary_tree = BinaryTree(N)

# 値設定
for _ in range(N):
    node_id, left, right = list(map(int, input().split()))
    binary_tree.set(node_id, left, right)

root = binary_tree.get_root()

print('Preorder')
binary_tree.walk_preorder(root)
print('\n', end = '')
print('Inorder')
binary_tree.walk_inorder(root)
print('\n', end = '')
print('Postorder')
binary_tree.walk_postorder(root)
print('\n', end = '')

Submission status: Accepted

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

def preParse(u):
    if u ==-1:
        return
    print(" %d"%(u),end = "")
    # print(u,end=' ')
    preParse(Nodes[u].left)
    preParse(Nodes[u].right)

def inParse(u):
    if u ==-1:
        return
    inParse(Nodes[u].left)
    print(" %d"%(u),end = "")

    # print(u,end=' ')
    inParse(Nodes[u].right)

def postParse(u):
    if u ==-1:
        return
    postParse(Nodes[u].left)
    postParse(Nodes[u].right)
    # print(u,end=' ')
    print(" %d"%(u),end = "")



def decode_node_data(n):
    '''
    n...受け取る文字列、一行ずつ
    一行ずつ、文字列からノードに変化する
    '''
    global Nodes
    num_of_elem = len(n)
    if num_of_elem < 2:
        raise ValueError
    elif num_of_elem == 2:  # leaf
        pass

    else:
        id, left,right = list(map(int,n))
        # まず、一人目の子供をとりあえず左に格納する
        Nodes[id].left = left
        if left!=-1:
            Nodes[left].parent=id
        
        Nodes[id].right = right
        if right !=-1 :
            Nodes[right].parent=id


MAX_NODES = 100001
Nodes = [Node(-1, None, None) for _ in range(MAX_NODES)]
if __name__ == "__main__":

    num_of_nodes = int(input())
    node_data = []
    for _ in range(num_of_nodes):
        node_data.append(input().split(' '))

    for n in node_data:
        decode_node_data(n)
    
    for i in range(num_of_nodes):
        if Nodes[i].parent==-1:
            root=i
    
    print('Preorder')
    preParse(root)
    print()
    
    print('Inorder')
    inParse(root)
    print()
    
    print('Postorder')
    postParse(root)
    print()

Submission status: Accepted

Solution code:
"""
与えられた二分木の全ての節点を体系的に訪問する
"""
import copy

class Node:
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.children = []

#空の木の構成
#node_idをインデックスに持たせる
n = int(input())
nodes = []
for _ in range(n):
    node = Node()
    nodes.append(node)

#木の構成
for i in range(n):
    l = list(map(int, input().split()))
    node_id = l[0]

    for j in range(2):
        try:
            child = l[1+j] #l[1+j]というのは子供の番号
            nodes[node_id].children.append(child) 
            if not child == -1:
                nodes[child].parent = node_id #子一人当たり親は必ず一人
        except:
            pass #エラー回避
    else:
        pass #子がいないとき

def getRoot(node_id):
    target = nodes[node_id]
    if target.parent == -1:
        return node_id

def preParse(node_id):
    if node_id == -1:
        return
    print(' '+str(node_id), end='')
    preParse(nodes[node_id].children[0])
    preParse(nodes[node_id].children[1])

def inParse(node_id):
    if node_id == -1:
        return
    inParse(nodes[node_id].children[0])
    print(' '+str(node_id), end='')
    inParse(nodes[node_id].children[1])

def postParse(node_id):
    if node_id == -1:
        return
    postParse(nodes[node_id].children[0])
    postParse(nodes[node_id].children[1])
    print(' '+str(node_id), end='')

root_id = 0
for i in range(n):
    target = nodes[i]
    if target.parent == -1:
        root_id = i
        break

print('Preorder')
preParse(root_id)
print('\nInorder')
inParse(root_id)
print('\nPostorder')
postParse(root_id)
print()

Submission status: Accepted

Solution code:
import sys

def preorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    route.append(nid)
    if left != -1: preorder_tree_walk(left, route)
    if right != -1: preorder_tree_walk(right, route)
    return route

def inorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    if left != -1: inorder_tree_walk(left, route)
    route.append(nid)
    if right != -1: inorder_tree_walk(right, route)
    return route

def postorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    if left != -1: postorder_tree_walk(left, route)
    if right != -1: postorder_tree_walk(right, route)
    route.append(nid)
    return route

n = int(input())
nodes = [[-1, -1, -1] for _ in range(n)]

for _ in range(n):
    nid, left, right = list(map(int, sys.stdin.readline().split()))
    nodes[nid][1] = left
    nodes[nid][2] = right

    if left != -1: nodes[left][0] = nid
    if right != -1: nodes[right][0] = nid

for nid, node in enumerate(nodes):
    root_nid = nid
    if node[0] == -1: break

preorder_route = preorder_tree_walk(root_nid, [])
inorder_route = inorder_tree_walk(root_nid, [])
postorder_route = postorder_tree_walk(root_nid, [])

print('Preorder')
print('', *preorder_route)
print('Inorder')
print('', *inorder_route)
print('Postorder')
print('', *postorder_route)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) 

class Node:
    def __init__(self, parent, left, right):
        self.p = parent
        self.l = left
        self.r = right


n = int(input())
node = {}
for i in range(n):
    node[i] = Node(-1, -1, -1)


for j in range(n):
    temp = list(map(int, input().split()))
    if temp[1] != -1:
        node[temp[0]].l = temp[1]
        node[temp[1]].p = temp[0]
    if temp[2] != -1:
        node[temp[0]].r = temp[2]
        node[temp[2]].p = temp[0]


def pre_parse(T, u, pre_list):
    if u == -1:
        return
    pre_list.append(u)
    pre_parse(T, T[u].l, pre_list)
    pre_parse(T, T[u].r, pre_list)

def in_parse(T, u, in_list):
    if u == -1:
        return
    in_parse(T, T[u].l, in_list)
    in_list.append(u)
    in_parse(T, T[u].r, in_list)

def post_parse(T, u, post_list):
    if u == -1:
        return
    post_parse(T, T[u].l, post_list)
    post_parse(T, T[u].r, post_list)
    post_list.append(u)


for k, v in node.items():
    if v.p == -1:
        root = k

pre_list = []
in_list = []
post_list = []
pre_parse(node, root, pre_list)
in_parse(node, root, in_list)
post_parse(node, root, post_list)

print('Preorder')
print('', *pre_list)
print('Inorder')
print('', *in_list)
print('Postorder')
print('', *post_list)

Submission status: Accepted

Solution code:
class BinaryNode():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = -1
        self.height = -1


class BinaryTree(list):
    def __init__(self, n):
        super().__init__([BinaryNode() for _ in range(n)])
        self.len = n
        self.root = None

    def set_node(self, id, left, right):
        self[id].left = left
        self[id].right = right
        if left > -1:
            self[left].parent = id
        if right > -1:
            self[right].parent = id

    def __set_depth(self, id, depth):
        self[id].depth = depth
        if self[id].left > -1:
            self.__set_depth(self[id].left, depth + 1)
        if self[id].right > -1:
            self.__set_depth(self[id].right, depth + 1)

    def set_depth(self):
        self.__set_depth(self.root, 0)

    def __set_height(self, id):
        if id == -1:
            return -1
        height = 1 + max(self.__set_height(self[id].left), self.__set_height(self[id].right))
        self[id].height = height
        return height

    def set_height(self):
        self.__set_height(self.root)

    def set_root(self):
        for i in range(self.len):
            if self[i].parent == -1:
                self.root = i
                break

    def get_nodetype(self, i):
        if self[i].parent == -1:
            return "root"
        elif self[i].left == -1 and self[i].right == -1:
            return "leaf"
        else:
            return "internal node"

    def get_sibling(self, i):
        parent = self[i].parent
        if parent == -1:
            return -1
        if self[parent].left == i:
            return self[parent].right
        else:
            return self[parent].left

    def get_degree(self, i):
        return (self[i].left > -1) * 1 + (self[i].right > -1) * 1

    def set_all(self):
        self.set_root()
        self.set_depth()
        self.set_height()

    def print(self):
        for i in range(self.len):
            print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
                i, self[i].parent, self.get_sibling(i), self.get_degree(i),
                self[i].depth, self[i].height, self.get_nodetype(i)))

    def __preorder(self, id):
        if id == -1:
            return []
        return [id] + self.__preorder(self[id].left) + self.__preorder(self[id].right)

    def order_str(self, order_type):
        if order_type == 0:
            order_list = self.__preorder(self.root)
        elif order_type == 1:
            order_list = self.__inorder(self.root)
        else:
            order_list = self.__postorder(self.root)

        return " ".join(map(str, order_list))

    def __inorder(self, id):
        if id == -1:
            return []
        return self.__inorder(self[id].left) + [id] + self.__inorder(self[id].right)

    def __postorder(self, id):
        if id == -1:
            return []
        return self.__postorder(self[id].left) + self.__postorder(self[id].right) + [id]


def main():
    n = int(input())
    tree = BinaryTree(n)
    for _ in range(n):
        node_info = input().split(" ")
        node_info = list(map(int, node_info))
        tree.set_node(node_info[0], node_info[1], node_info[2])
    tree.set_all()
    print("Preorder")
    print(" " + tree.order_str(0))
    print("Inorder")
    print(" " + tree.order_str(1))
    print("Postorder")
    print(" " + tree.order_str(2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
nil=-1
t=[[-1,-1,-1]for _ in range(n)]
for i in range(n):
	a,b,c=map(int,input().split())
	if b!=-1:
		t[b][0]=a
		t[a][1]=b
	if c!=-1:
		t[c][0]=a
		t[a][2]=c
cnt=0
for i in range(n):
	if t[i][0]==-1:
		root=i
		break
def pre(u):
	if u==nil:
		return
	print(" "+str(u),end="")
	pre(t[u][1])
	pre(t[u][2])
def pre2(u):
	if u==nil:
		return
	pre2(t[u][1])
	print(" "+str(u),end="")
	pre2(t[u][2])
def pre3(u):
	if u==nil:
		return
	pre3(t[u][1])
	pre3(t[u][2])
	global cnt
	if cnt==n-1:
		print(" "+str(u))
	else:
		print(" "+str(u),end="")
	cnt+=1
print("Preorder")
pre(root)
print("\n"+"Inorder")
pre2(root)
print("\n"+"Postorder")
pre3(root)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


null = -1

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

def preParse(u):
    if u == null:
        return
    print(" ", end = "")
    print(Tree[u].id, end = "")
    preParse(Tree[u].left)
    preParse(Tree[u].right)
    
def inParse(u):
    if u == null:
        return
    inParse(Tree[u].left)
    print(" ", end = "")
    print(Tree[u].id, end = "")
    inParse(Tree[u].right)
    
def postParse(u):
    if u == null:
        return
    postParse(Tree[u].left)
    postParse(Tree[u].right)
    print(" ", end = "")
    print(Tree[u].id, end = "")


Tree = []
root = 0

n = int(input())
for i in range(n):
    Tree.append(Node())
    
for i in range(n):
    tmp = list(map(int, input().split()))
    
    Tree[tmp[0]].id = tmp[0]
    
    if tmp[1] != -1:
        Tree[tmp[0]].left = tmp[1]
        Tree[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        Tree[tmp[0]].right = tmp[2]
        Tree[tmp[2]].parent = tmp[0]

for i in range(n):
    if Tree[i].parent == null:
        root = i
        break

print("Preorder\n", end = "")
preParse(root)
print("\nInorder")
inParse(root)
print("\nPostorder")
postParse(root)
print("")

Submission status: Accepted

Solution code:
N = int(input())
childs = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]
for _ in range(N):
    i, l, r = map(int, input().split())
    childs[i].extend([l, r])
    for child in [l, r]:
        if child != -1:
            parent[child] = i

preorder = []
inorder = []
postorder = []


def dfs(cur):
    preorder.append(cur)
    [left, right] = childs[cur]
    if left != -1:
        dfs(left)
    inorder.append(cur)
    if right != -1:
        dfs(right)
    postorder.append(cur)


root = 0
while root < N:
    if parent[root] == -1:
        break
    else:
        root += 1
dfs(root)


print('Preorder')
print(' ' + ' '.join(map(str, preorder)))
print('Inorder')
print(' ' + ' '.join(map(str, inorder)))
print('Postorder')
print(' ' + ' '.join(map(str, postorder)))

Submission status: Accepted

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

def preorder(tree, root):
    if root == -1:
        pass
    else:
        print(' %d' % root, end='')
        preorder(tree, tree[root].left)
        preorder(tree, tree[root].right)

def inorder(tree, root):
    if root == -1:
        pass
    else:
        inorder(tree, tree[root].left)
        print(' %d' % root, end='')
        inorder(tree, tree[root].right)

def postorder(tree, root):
    if root == -1:
        pass
    else:
        postorder(tree, tree[root].left)
        postorder(tree, tree[root].right)
        print(' %d' % root, end='')

if __name__ == '__main__':
    n = int(input())
    tree = {}
    root = -1
    for _ in range(n):
        datas = [int(num) for num in input().split(' ')]
        nodeid = datas[0]
        if nodeid not in tree.keys():
            tree[nodeid] = Node(nodeid)
        tree[nodeid].left = left = int(datas[1])
        tree[nodeid].right = right = int(datas[2])
        if left != -1:
            if left not in tree.keys():
                tree[left] = Node(left)
            tree[left].parent = nodeid
        if right != -1:
            if right not in tree.keys():
                tree[right] = Node(right)
            tree[right].parent = nodeid

    for i in range(n):
        if tree[i].parent == -1:
            # this is root
            root = i
            break
            
    print('Preorder')
    preorder(tree, root)
    print()

    print('Inorder')
    inorder(tree, root)
    print()

    print('Postorder')
    postorder(tree, root)
    print()

Submission status: Accepted

Solution code:
#1_7_C
N = int(input())

preorder_list = []
inorder_list = []
postorder_list = []

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, left, right = list(map(int, row.split()))
    rooted_tree[id]["id"] = id
    rooted_tree[id]["right"] = right
    rooted_tree[id]["left"] = left
    #子供のparentを左右で設定する。
    if left > -1:
        left_child_id = left
        rooted_tree[left_child_id]["parent"] = id
    if right > -1:
        right_child_id = right
        rooted_tree[right_child_id]["parent"] = id
        
def preParse(node):
    preorder_list.append(node["id"])
    if node["left"] != -1:
        preParse(rooted_tree[node["left"]])
    if node["right"] != -1:
        preParse(rooted_tree[node["right"]])
    
def inParse(node):
    if node["left"] != -1:
        inParse(rooted_tree[node["left"]])
    inorder_list.append(node["id"])
    if node["right"] != -1:
        inParse(rooted_tree[node["right"]])
    
def postParse(node):
    if node["left"] != -1:
        postParse(rooted_tree[node["left"]])
    if node["right"] != -1:
        postParse(rooted_tree[node["right"]])
    postorder_list.append(node["id"])
    
def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

for node in rooted_tree:
    if get_parent(node) == -1:
        root_id = node["id"]
        break

print("Preorder")
preParse(rooted_tree[root_id])
print(" "+" ".join(map(str, preorder_list)))
# print(*preorder_list)
print("Inorder")
inParse(rooted_tree[root_id])
# print(*inorder_list)
print(" "+" ".join(map(str, inorder_list)))
print("Postorder")
postParse(rooted_tree[root_id])
# print(*postorder_list)
print(" "+" ".join(map(str, postorder_list)))

Submission status: Accepted

Solution code:
def prePhase(u):
    left,right=T[u]
    if u==-1:return
    print(" {}".format(u), end="")
    prePhase(left)
    prePhase(right)


def inPhase(u):
    left,right=T[u]
    if u==-1:return
    inPhase(left)
    print(" {}".format(u), end="")
    inPhase(right)


def postPhase(u):
    left,right=T[u]
    if u==-1:return
    postPhase(left)
    postPhase(right)
    print(" {}".format(u), end="")


n=int(input())
A=sorted([list(map(int,input().split())) for i in range(n)])
T=[]
top=[i for i in range(n)]
for i in range(n):
    B=A[i]
    node,left,right=B[0],B[1],B[2]
    if left!=-1:top.remove(left)
    if right!=-1:top.remove(right)
    T.append([left,right])
top=top[0]

print("Preorder")
prePhase(top)
print()
print("Inorder")
inPhase(top)
print()
print("Postorder")
postPhase(top)
print()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u):
        lu, ru = chi[u]
        pre.append(u)
        if lu != -1: dfs(lu)
        ino.append(u)
        if ru != -1: dfs(ru)
        pos.append(u)

    n = int(input())
    par = [-1] * n
    chi = [[] for _ in range(n)]
    for _ in range(n):
        u, l, r = map(int, input().split())
        if l != -1: par[l] = u
        if r != -1: par[r] = u
        chi[u] += [l]
        chi[u] += [r]

    root = par.index(-1)
    pre = []
    ino = []
    pos = []
    dfs(root)

    print("Preorder")
    print("", *pre)
    print("Inorder")
    print("", *ino)
    print("Postorder")
    print("", *pos)

main()