L2-011 玩转二叉树 (25 分) java

1. 通过先序序列、中序序列还原二叉树 可参考：https://blog.csdn.net/weixin_51995229/article/details/124298623
2. 二叉树的层次遍历可参考：https://blog.csdn.net/weixin_51995229/article/details/124197521
3. 此题就是先通过先序序列、中序序列还原二叉树 ，然后层次遍历
4. 此题需要镜面反转，是指将所有非叶结点的左右孩子对换。所以我们在遍历的时候，先遍历右子树即可；

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[] pre = new int[n];
        int[] in = new int[n];
        //先输入的是中序序列
        for (int i = 0; i < n; i++) {
            in[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            pre[i] = sc.nextInt();
        }
        Tree t = Tree.createTree(pre, in);
        t.levelOrder();
    }
}

class Tree {
    Node root;

    public Tree() {
        root = new Node();
    }

    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)
                System.out.print(t.data);
            else
                System.out.print(" " + t.data);
            f++;
            //先遍历右孩子，即可将所有非叶结点的左右孩子对换
            if (t.right != null)
                q.offer(t.right);
            if (t.left != null)
                q.offer(t.left);

        }
    }

    public static Tree createTree(int[] pre, int[] in) {
        Tree res = new Tree();
        res.root = createTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return res;
    }

    private static Node createTree(int[] pre, int s1, int end1, int[] in, int s2, int end2) {
        //递归出口不能忘
        if (s1 > end1 || s2 > end2)
            return null;
        Node root = new Node(pre[s1]);
        for (int i = s2; i <= end2; i++) {
            if (in[i] == pre[s1]) {
                root.left = createTree(pre, s1 + 1, s1 + i - s2, in, s2, i - 1);
                root.right = createTree(pre, s1 + i - s2 + 1, end1, in, i + 1, end2);
                break;
            }
        }
        return root;
    }
}

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

    public Node() {
    }

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