题解 | 先序遍历、中序遍历和后序遍历（新年快乐，新年第一题还是比较友善的）

# 由于节点编号连续，构建一个哈希表保存所有节点
# 通过一个children表获取根节点索引 -- 是孩子则对应下标的值改为1，则唯一一个为0的为根节点索引
import sys

class Node:
    __slots__ = ("val", "left", "right")  # 减少内存占用

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


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])

    # 特殊情况：单节点树
    if n == 1:
        print("1\n1\n1")
        return

    # 初始化数据结构
    nodes = [None] * (n + 1)            # 节点列表
    edges = [[] for _ in range(n + 1)]  # 临时存储边关系
    is_child = [0] * (n + 1)            # 标记是否为子节点
    is_child[0] = 1                     # 排除边界哨兵

    # 解析边并记录父子关系
    idx = 1
    for _ in range(n - 1):
        parent, child = int(data[idx]), int(data[idx + 1])
        idx += 2
        edges[parent].append(child)
        is_child[child] = 1

    # 1. 创建所有节点
    for i in range(1, n + 1):
        nodes[i] = Node(i)

    # 2. 构建树结构（可以和解析边放一起，这样不用多花 o(n) 的时空储存边关系，但糅合在一起有有点乱，且连接时需要判断是否已经有子节点，会导致两个子节点的进行两次处理，それわちょっと.jpg）
    for parent_val in range(1, n + 1):

        parent = nodes[parent_val]
        children_vals = sorted(edges[parent_val])  # 按规则排序子节点

        if len(children_vals) == 1:
            # 单子节点规则：大于父节点为左，否则为右
            child_val = children_vals[0]
            child_node = nodes[child_val]
            if child_val > parent_val:
                parent.left = child_node
            else:
                parent.right = child_node
        elif len(children_vals) == 2:  # 两个子节点
            # 小值为左，大值为右
            parent.left = nodes[children_vals[0]]
            parent.right = nodes[children_vals[1]]
        else:  # 叶节点
            pass

    # 3. 查找根节点（不为任何节点的子节点）
    root_val = is_child.index(0)
    root = nodes[root_val]

    # 先序遍历
    def get_preoder(root, ans: list[str]):
        if root == None:
            return

        ans.append(str(root.val))
        get_preoder(root.left, ans)
        get_preoder(root.right, ans)

    # 中序遍历
    def get_inoder(root, ans: list[str]):
        if root == None:
            return

        get_inoder(root.left, ans)
        ans.append(str(root.val))
        get_inoder(root.right, ans)

    # 后序遍历
    def get_postoder(root, ans: list[str]):
        if root == None:
            return

        get_postoder(root.left, ans)
        get_postoder(root.right, ans)
        ans.append(str(root.val))

    # 4. 输出结果
    preorder = []
    get_preoder(root, preorder)
    print(" ".join(preorder))
    inorder = []
    get_inoder(root, inorder)
    print(" ".join(inorder))
    postorder = []
    get_postoder(root, postorder)
    print(" ".join(postorder))


if __name__ == "__main__":
    main()

难点在于不知道root，而是直接用邻接表创建树（大概）