已知后序遍历和中序遍历,建树,然后输出层序遍历(不建树也可以)
时间限制
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系统提交代码要去掉所有中文注释,不然会编译错误