二叉树已知层序&中序，求先序&后序

子树层序遍历的序列结果，与父树层序遍历结果中的相对位置相同：

import java.util.*;
class Tree{
    int val;
    Tree left, right;
    Tree(int a){val = a;}
}
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] str1 = sc.nextLine().split(" ");
        String[] str2 = sc.nextLine().split(" ");
        List<Integer> v1 = new ArrayList<>();
        List<Integer> v2 = new ArrayList<>();
        for(int i = 0; i < str1.length; ++i) v1.add(Integer.valueOf(str1[i]));
        for(int i = 0; i < str2.length; ++i) v2.add(Integer.valueOf(str2[i]));
        Tree r = f(v1, v2);//先把这棵树求出来
        p(y(r));//p是打印方法，y是叶节点方法
        p(g(r));//g是先序方法
        p(h(r));//h是后序方法
    }
    public static Tree f(List<Integer> v1, List<Integer> v2){//求出这棵树
        if(v1.isEmpty() || v2.isEmpty()) return null;
        Tree r = new Tree(v1.get(0));//层序的第一个节点就是根节点
        int temp = v2.indexOf(v1.get(0));//找出根节点在中序的位置
        List<Integer> v11 = new ArrayList<>();//左子树的层序
        List<Integer> v12 = new ArrayList<>();//右子树的层序
        List<Integer> v21 = v2.subList(0, temp);//中序根左边是左子树
        List<Integer> v22 = v2.subList(temp + 1, v2.size());//中序根右边是右子树
        for(int i = 1; i < v1.size(); ++i){
            if(v21.contains(v1.get(i))) v11.add(v1.get(i));//左子树的层序
        }
        for(int i = 1; i < v1.size(); ++i){
            if(v22.contains(v1.get(i))) v12.add(v1.get(i));//右子树的层序
        }
        r.left = f(v11, v21);
        r.right = f(v12, v22);
        return r;
    }
    public static List<Integer> g(Tree r){//先根遍历
        List<Integer> v = new ArrayList<>();
        if(r == null) return v;
        v.add(r.val);//先根
        for(Integer i : g(r.left)) v.add(i);
        for(Integer i : g(r.right)) v.add(i);
        return v;
    }
    public static List<Integer> h(Tree r){//后根遍历
        List<Integer> v = new ArrayList<>();
        if(r == null) return v;
        for(Integer i : h(r.left)) v.add(i);
        for(Integer i : h(r.right)) v.add(i);
        v.add(r.val);//后根
        return v;
    }
    public static List<Integer> y(Tree r){//求叶节点
        List<Integer> v = new ArrayList<>();
        if(r == null) return v;
        if(r.left == null && r.right == null) v.add(r.val);//叶节点左右皆空
        for(Integer i : y(r.left)) v.add(i);
        for(Integer i : y(r.right)) v.add(i);
        return v;
    }
    public static void p(List<Integer> v){
        if(v.isEmpty()) return;
        System.out.print(v.get(0));//打印第一个
        for(int i = 1; i < v.size(); ++i){
            System.out.print(" ");
            System.out.print(v.get(i));
        }
        System.out.println();//打完记得换行
    }
}