1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

// 使用数组模拟指针，lc[i] 存储节点 i 的左孩子，rc[i] 存储右孩子
    private static int[] lc, rc;

    // 使用 StringBuilder 缓存结果
    private static StringBuilder preOrder = new StringBuilder();
    private static StringBuilder inOrder = new StringBuilder();
    private static StringBuilder postOrder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 PrintWriter 提升大规模数据下的 I/O 效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine().trim());

        // 边界情况：空树
        if (n == 0) {
            return;
        }

        // 初始化结构：n+1 长度是为了匹配从 1 开始的节点编号
        lc = new int[n + 1];
        rc = new int[n + 1];
        boolean[] hasParent = new boolean[n + 1]; // 用于寻找根节点（根节点没有父节点）

        // 使用邻接表暂时存储“父 -> 子”的原始指向关系，随后再按规则分配左右
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        // 读取 n-1 条边，构建树的层级关系
        for (int i = 0; i < n - 1; i++) {
            String[] edge = br.readLine().trim().split("\\s+");
            int u = Integer.parseInt(edge[0]); // 父节点
            int v = Integer.parseInt(edge[1]); // 子节点
            adj[u].add(v);
            hasParent[v] = true; // 只要被指向，就说明该节点不是根节点
        }

        /**
         * 根据题目定义的规则，将 adj 里的子节点分配到 lc 或 rc
         */
        for (int i = 1; i <= n; i++) {
            // 父节点拥有两个孩子
            if (adj[i].size() == 2) {
                int c1 = adj[i].get(0);
                int c2 = adj[i].get(1);
                // 编号小者为左，大者为右
                lc[i] = Math.min(c1, c2);
                rc[i] = Math.max(c1, c2);
            }
            // 父节点仅有一个孩子
            else if (adj[i].size() == 1) {
                int child = adj[i].get(0);
                // 子节点编号 > 父节点编号 ➜ 视为左孩子；反之 ➜ 视为右孩子
                if (child > i) {
                    lc[i] = child;
                } else {
                    rc[i] = child;
                }
            }
        }

        // 寻找整棵树的唯一根节点
        int root = 1;
        for (int i = 1; i <= n; i++) {
            if (!hasParent[i]) {
                root = i;
                break;
            }
        }

        // 从根节点开始DFS
        traverse(root);

        // 格式化输出
        out.println(preOrder.toString().trim());
        out.println(inOrder.toString().trim());
        out.println(postOrder.toString().trim());

        // 刷新缓冲区确保数据完整写出并关闭流
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 深度优先遍历 (DFS) 方法
     *
     * @param cur 当前正在访问的节点索引
     */
    private static void traverse(int cur) {
        // 基准情形：如果当前节点为 0，说明触碰到了空叶子节点，停止向下延伸
        if (cur == 0) {
            return;
        }

        /**
         * 1. 先序遍历 (Pre-order)：[中] -> 左 -> 右
         * 刚进入当前节点时立即记录。
         */
        preOrder.append(cur).append(" ");

        // 向左延伸
        traverse(lc[cur]);

        /**
         * 2. 中序遍历 (In-order)：左 -> [中] -> 右
         * 当左子树全部处理完毕回溯到当前点时记录。
         */
        inOrder.append(cur).append(" ");

        // 向右延伸
        traverse(rc[cur]);

        /**
         * 3. 后序遍历 (Post-order)：左 -> 右 -> [中]
         * 当左右子树全部处理完毕，即将彻底离开当前点时记录。
         */
        postOrder.append(cur).append(" ");
    }