题解 | 先序遍历、中序遍历和后序遍历

import sys

class TreeNode:
    def __init__(self, x):
        self.id = x
        self.l_child = None
        self.r_child = None

def preorder(root, res):
    if root is None:
        return
    res.append(root.id)
    preorder(root.l_child, res)
    preorder(root.r_child, res)

def inorder(root, res):
    if root is None:
        return
    inorder(root.l_child, res)
    res.append(root.id)
    inorder(root.r_child, res)

def postorder(root, res):
    if root is None:
        return
    postorder(root.l_child, res)
    postorder(root.r_child, res)
    res.append(root.id)

n = int(sys.stdin.readline())
nodes = [TreeNode(i) for i in range(n+1)]  # 1-based indexing

# 记录每个节点的子节点列表
children_dict = [[] for _ in range(n+1)]

# 记录哪些节点被指向了，有助于找到根节点
has_father = [False] * (n+1)

for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    children_dict[a].append(b)
    has_father[b] = True

# 找根节点，根节点没父亲
root_id = 0
for i in range(1, n+1):
    if not has_father[i]:
        root_id = i
        break

# 根据规则给每个节点设置左右孩子
for i in range(1, n+1):
    kids = children_dict[i]
    if len(kids) == 2:
        left = min(kids)
        right = max(kids)
        nodes[i].l_child = nodes[left]
        nodes[i].r_child = nodes[right]
    elif len(kids) == 1:
        c = kids[0]
        # 规则：如果孩子编号 > 父编号，则是左孩子，否则右孩子
        if c > i:
            nodes[i].l_child = nodes[c]
        else:
            nodes[i].r_child = nodes[c]

# 遍历输出
pre_res, in_res, post_res = [], [], []
preorder(nodes[root_id], pre_res)
inorder(nodes[root_id], in_res)
postorder(nodes[root_id], post_res)

print(' '.join(map(str, pre_res)))
print(' '.join(map(str, in_res)))
print(' '.join(map(str, post_res)))