java实现 已知一颗树的层序遍历和中序遍历 输出树的先序遍历和后序遍历

给定树的节点数，在给出这棵树的层序遍历和中序遍历

输出这棵树的先序遍历和后序遍历

输入

7
3 5 4 2 6 7 1
2 5 3 6 4 7 1

输出

3 5 2 4 6 7 1
2 5 6 1 7 4 3

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

class Node {
    int data;
    Node left, right;
    public Node(){
        ;
    }
    public Node(int item) {
        data = item;

    }
}

class Tree {
    private HashMap<Integer, Integer> inorderMap;
    public Tree(int[] inOrder, int[] levelOrder){
        inorderMap = new HashMap<>();
        for (int i = 0; i < inOrder.length; i++) {
            inorderMap.put(inOrder[i], i);
        }
    }
    public Node build(int[] levelOrder, int[] inOrder, int inorderStart, int inorderEnd){
        if(inorderStart > inorderEnd){
            return null;
        }
        int rootIndex = 0;
        for(int i = 0; i < levelOrder.length; i++){
            if(inorderStart <= inorderMap.get(levelOrder[i]) && inorderMap.get(levelOrder[i]) <= inorderEnd){
                rootIndex = inorderMap.get(levelOrder[i]);
                break;
            }
        }
        Node root = new Node(inOrder[rootIndex]);

        if(rootIndex > inorderStart) {
            root.left = build(levelOrder,  inOrder, inorderStart, rootIndex - 1);
        }
        if(rootIndex < inorderEnd) {
            root.right = build(levelOrder, inOrder, rootIndex + 1, inorderEnd);
        }

        return root;
    }

    public void preOrder (Node root, List<Integer> pre_ans){
        if(root != null){
            pre_ans.add(root.data);
            preOrder(root.left, pre_ans);
            preOrder(root.right, pre_ans);
        }
    }

    public void postOrder (Node root, List<Integer> post_ans){
        if(root != null){
            postOrder(root.left, post_ans);
            postOrder(root.right, post_ans);
            post_ans.add(root.data);
        }
    }

}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] levelOrder = new int[n];
        for (int i = 0; i < n; i++) {
            levelOrder[i] = scanner.nextInt();
        }

        int[] inOrder = new int[n];
        for (int i = 0; i < n; i++) {
            inOrder[i] = scanner.nextInt();
        }

        scanner.close();

        Tree tree = new Tree(inOrder, levelOrder);
        Node root = tree.build(levelOrder, inOrder, 0, n - 1);

        List<Integer> pre_ans = new ArrayList<>();
        List<Integer> post_ans = new ArrayList<>();
        tree.preOrder(root, pre_ans);
        print(pre_ans);
        System.out.println();
        tree.postOrder(root, post_ans);
        print(post_ans);
    }

    public static void print(List<Integer> ans){
        boolean flag = true;
        for (int i = 0; i < ans.size(); i++) {
            if(!flag){
                System.out.print(" ");
            }
            System.out.print(ans.get(i));
            flag = false;
        }
    }
}