（团体程序设计天梯赛）L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

4 6 1 7 5 3 2

因为输出的是镜像，所以只需让右子树先进队即可。其它几乎和(团体程序设计天梯赛)L2-006 树的遍历
一样，只是一个给前序遍历，一个给后序遍历。其它基本没差别

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));

    static int bc[];

    public static void main(String[] args) {
        int n = nextInt();
        int q[] = new int[n+1];
        int z[] = new int[n+1];
        for(int i = 0;i<n;i++) &#123;
            z[i] = nextInt();
        &#125;
        for(int i = 0;i<n;i++) &#123;
            q[i] = nextInt();
        &#125;
        int c[] = new int[n+1];
        Queue<Node> que = new LinkedList<Node>();
        que.add(new Node(0, n, 0, n));
        int cont = 0;
        while(!que.isEmpty()) &#123;
            Node te = que.poll();
            c[cont++] = q[te.ql];
            for(int i = te.zl;i<te.zr;i++) &#123;
                if(z[i]==q[te.ql]) &#123;
                    if(i<te.zr-1) &#123;
                        que.add(new Node(i-te.zl+te.ql+1, te.qr, i+1, te.zr));                        
                    &#125;
                    if(i>te.zl) &#123;
                        que.add(new Node(te.ql+1, i-te.zl+te.ql, te.zl, i));
                    &#125;
                    
                    break;
                &#125;
            &#125;
        &#125;
        System.out.print(c[0]);
        for(int i = 1;i<n;i++) &#123;
            System.out.print(" "+c[i]);
        &#125;
    &#125;

    static int nextInt() &#123;
        try &#123;
            st.nextToken();
        &#125; catch (IOException e) &#123;
            e.printStackTrace();
        &#125;
        return (int) st.nval;
    &#125;

    static String next() &#123;
        try &#123;
            st.nextToken();
        &#125; catch (IOException e) &#123;
            e.printStackTrace();
        &#125;
        return st.sval;
    &#125;
&#125;
class Node&#123;
    int ql;
    int qr;
    int zl;
    int zr;
    public Node(int ql, int qr, int zl, int zr) &#123;
        this.ql = ql;
        this.qr = qr;
        this.zl = zl;
        this.zr = zr;
    &#125;
    @Override
    public String toString() &#123;
        return "Node [ql=" + ql + ", qr=" + qr + ", zl=" + zl + ", zr=" + zr + "]";
    &#125;
    
&#125;