L2-006. 树的遍历

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

输入格式：

输入第一行给出一个正整数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.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

public class Main {
    public static int[] post = new int[31];
    public static int[] in = new int[31];

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            post[i] = cin.nextInt();
        }
        for (int i = 0; i < n; ++i) {
            in[i] = cin.nextInt();
        }
        cin.close();
        Node node = createTree(post, 0, in, 0, n);
        cengxu(node);
    }

    public static void cengxu(Node node) {
        Queue<Node> queue = new LinkedList<Node>();
        Node p = node;
        if (p != null) {
            queue.add(p);
            boolean flag = true;
            while (!queue.isEmpty()) {
                p = queue.poll();
                if (flag) {
                    System.out.print(p.data);
                    flag = false;
                } else {
                    System.out.print(" " + p.data);
                }
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
        }
    }
    // 已知中序后序，然后建树
    public static Node createTree(int[] post, int pi, int[] in, int ini, int n) {
        if (n <= 0) {
            return null;
        }
        Node node = new Node();
        node.data = post[pi + n - 1]; // 最后一个一定是该树根节点
        int i;
        for (i = 0; i < n; ++i) {
            if (in[ini + i] == node.data)
                break;
        }
        // 这里的下标pi,ini是什么?是数组起点,因为c++可以post+pi=>&post[pi]来改变数组首地址，但java不行，要记录起始下标
        node.left = createTree(post, pi, in, ini, i);//最后一个参数表示该树有多少个结点，有i个，左子树第一次有3个结点
        // 相当于c++里面createTree(post+pi, in+ini, i);
        // 以中序遍历为界，左边是左子树，右边是右子树
        // 例子后序  2 3 1    5 7 6   4
        //     中序 1 2 3  4  5 6 7
        node.right = createTree(post, pi + i, in, ini + i + 1, n - i - 1);//有n-i-1个，即第一次右子树有7-3-1=3个结点
        return node;
    }
}

顺带说一下，PTA系统提交代码要去掉所有中文注释，不然会编译错误

题目链接地址https://www.patest.cn/contests/gplt/L2-006

========================================Talk is cheap, show me the code=======================================