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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = 0;
        // 注意 hasNext 和 hasNextLine 的区别
        if (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();
        }

        // tree存储n个节点
        int[][] tree = new int[n + 1][2];  // 0为左子树，1为右子树
        boolean[] hasparent = new boolean[n + 1];

        // 共存储n-1个边，树的节点和边的关系满足n-1，数组从1开始计数
        for(int i = 1;i < n;i++){
            if (in.hasNextInt()) { // 注意 while 处理多个 case
                int a = in.nextInt();
                int b = in.nextInt();

                // 空树
                if(tree[a][0] == 0 && tree[a][1] == 0){
                    if( a > b){
                        tree[a][1] = b;
                    }else{
                        tree[a][0] = b;
                    }
                    hasparent[b] = true;
                    // 非空树
                }else{
                    // 左子树不为空，则比较左子树和b的大学
                    if(tree[a][0] > 0){
                        // 左子树小于b，则赋值给右子树
                        if(tree[a][0] < b){
                            tree[a][1] = b;
                        }else{
                            // 左子树大于b值，交换左右子树
                            int temp = tree[a][0];
                            tree[a][0] = b;
                            tree[a][1] = temp;
                        }

                    // 左子树为空
                    }else{
                        // 右子树大于b，赋值左子树
                        if(tree[a][1] > b){
                            tree[a][0] = b;
                        }else{
                            // 右子树小于b值，交换左右子树
                            int temp = tree[a][1];
                            tree[a][1] = b;
                            tree[a][0] = temp;
                        }
                    }
                    hasparent[b] = true;

                }

            }
        }

        // 只有一个节点，即为根节点，不需要输入边，默认根节点为1
        int root = 1;
        // 找根节点，入度为0的即为根节点
        for(int i = 1;i < n;i++){
            if(!hasparent[i]){
                root = i;
                break;
            }
        }

        // 先序遍历 根，左右
        previstiedTree(tree,root);
        System.out.println();

        // 中序左，根，右
        midvistiedTree(tree,root);
        System.out.println();

        // 后序左右，根
        lastvistiedTree(tree,root);
        System.out.println();

    }

    // 先序遍历
    public static void previstiedTree(int[][] tree,int root){

        // 根子树有节点则拜访，否则为叶子节点，返回
        if(root > 0){
            // 拜访根节点
            System.out.printf("%d ",root);
            // 左子树
            previstiedTree(tree,tree[root][0]);

            // 右子树
            previstiedTree(tree,tree[root][1]);
        }

    }

    // 中序遍历
    public static void midvistiedTree(int[][] tree,int root){

        // 根子树有节点则拜访，否则为叶子节点，返回
        if(root > 0){
            // 左子树
            midvistiedTree(tree,tree[root][0]);

            // 拜访根节点
            System.out.printf("%d ",root);

            // 右子树
            midvistiedTree(tree,tree[root][1]);
        }

    }


    // 后序遍历
    public static void lastvistiedTree(int[][] tree,int root){

        // 根子树有节点则拜访，否则为叶子节点，返回
        if(root > 0){
            // 左子树
            lastvistiedTree(tree,tree[root][0]);

            // 右子树
            lastvistiedTree(tree,tree[root][1]);

            // 拜访根节点
            System.out.printf("%d ",root);
        }

    }
}