(团体程序设计天梯赛)L2-006 树的遍历

题目链接

L2-006 树的遍历 （25 分）
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

4 1 6 3 5 7 2

给出数的后序和中序，要求输出二叉树的层次遍历。层次遍历用队列进行实现进行先进左子树后进右子树，将根放入，就可以了

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

    static int out[] = new int[32];//层次遍历结果
    static int next=0;

    static int hx[] = new int[32];
    static int zx[] = new int[32];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = nextNum();
        for (int i = 0; i < N; i++) &#123;
            hx[i] = nextNum();
        &#125;
        for (int i = 0; i < N; i++) &#123;
            zx[i] = nextNum();
        &#125;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, N, 0, N));
        while(!q.isEmpty()) &#123;
            Node n = q.poll();
            int t = hx[n.hr-1];
            out[next++] = hx[n.hr-1];
            for(int i = n.zl;i<n.zr;i++) &#123;
                if(zx[i]==hx[n.hr-1]) &#123;
                    if(i>n.zl) &#123;
                        q.add(new Node(n.zl, i, n.hl,n.hl+(i-n.zl) ));//左子树进队
                    &#125;
                    if(i<n.zr-1) &#123;
                        q.add(new Node(i+1, n.zr, n.hr-(n.zr-i),n.hr-1)); //右子树进队
                    &#125;
                    break;
                &#125;
            &#125;
        &#125;
        System.out.print(out[0]);
        for(int i = 1;i<N;i++)
            System.out.print(" "+out[i]);
        
    &#125;
    
    private static int nextNum() &#123;
        try &#123;
            st.nextToken();
        &#125; catch (IOException e) &#123;
            e.printStackTrace();
        &#125;
        return (int) st.nval;

    &#125;
&#125;
class Node&#123;
    int zl;
    int zr;
    int hl;
    int hr;
    /**
     * @param zl 中序数组左索引
     * @param zr 中序数组右索引
     * @param hl 后序数组左索引
     * @param hr 后序数组右索引
     */
    public Node(int zl, int zr, int hl, int hr) &#123;
        this.zl = zl;
        this.zr = zr;
        this.hl = hl;
        this.hr = hr;
    &#125;
    @Override
    public String toString() &#123;
        return "Node [zl=" + zl + ", zr=" + zr + ", hl=" + hl + ", hr=" + hr + "]";
    &#125;
&#125;