L2-006 树的遍历 (25 分)

1. 关于通过后序、中序创建二叉树，请看：https://blog.csdn.net/weixin_51995229/article/details/124301027
   需要注意数组开的大小要正好为结点数，因为在构造时候用的是数组的长度作为的子树区间终点；也可以在构造方法中多加一个参数，用来指定结点的个数，这样可以随意创建数组的大小；
2. 关于二叉树的层次遍历，请看：https://blog.csdn.net/weixin_51995229/article/details/124197521
3. 此题我们将二叉树构造好，再调用一个层次遍历方法即可；

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] in = new int[n];
        int[] post = new int[n];
        for (int i = 0; i < n; i++) {
            post[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            in[i] = sc.nextInt();
        }
        //通过后序、中序构造二叉树
        Tree t = Tree.createTree(post, in);
        t.levelOrder();
    }
}

class Tree {
    Node root;

    public Tree() {
        this.root = null;
    }

    //层次遍历
    private int f = 0;

    public void levelOrder() {
        Queue q = new LinkedList<>();
        if (root != null)
            q.offer(root);
        //输出队列的第一个结点，然后将其出队，如果其有孩子，将其左右孩子入队，至到队列为空
        while (!q.isEmpty()) {
            Node t = q.poll();//队列的第一个结点
            if (f == 0) {
                f = 1;
                System.out.print(t.data);
            } else {
                System.out.print(" " + t.data);
            }
            //需要判断它是否有孩子，有的话再入队
            if (t.left != null)
                q.offer(t.left);
            if (t.right != null)
                q.offer(t.right);
        }
    }

    //二叉树的构造
    public static Tree createTree(int[] post, int[] in) {
        Tree res = new Tree();
        res.root = createTree(post, 0, post.length - 1, in, 0, in.length - 1);
        return res;
    }

    
    private static Node createTree(int[] post, int s1, int end1, int[] in, int s2, int end2) {
        if (s1 > end1 || s2 > end2)
            return null;
        Node root = new Node(post[end1]);//后序序列的最后一个结点为根节点
        for (int i = s2; i <= end2; i++) {//找根节点在中序序列中的位置，从而可以找左右子树
            if (post[end1] == in[i]) {
                root.left = createTree(post, s1, s1 + i - s2 - 1, in, s2, i - 1);//对于左子树end1需要-1，因为不像先序那样，第一个结点为根节点
                root.right = createTree(post, s1 + i - s2, end1 - 1, in, i + 1, end2);//对于右子树end1需要-1，因为最后一个结点为根节点
                break;
            }
        }
        return root;
    }
}

class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }
}