L2-035 完全二叉树的层序遍历(Java)
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
题目
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 的,有 个结点的二叉树,若其结点对应于相同深度完美二叉树的层序遍历的前 个结点,这样的树就是完全二叉树。
给定一棵完全二叉树的后序遍历,请你给出这棵树的层序遍历结果。
输入格式:
输入在第一行中给出正整数 ,即树中结点个数。第二行给出后序遍历序列,为 个不超过 100 的正整数。同一行中所有数字都以空格分隔。
输出格式:
在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
sh
8
91 71 2 34 10 15 55 18
输出样例:
sh
18 34 55 71 2 10 15 91
sh
代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
题解
我们知道,二叉树的后序遍历是左右根,我们可以根据这个顺序,每次找到根的时候,将这个节点存储起来。而完全二叉树中,我们可以根据层序遍历给每个节点从 1 到 n 进行编号,由公式可知每个节点的左右节点编号为 、。
代码如下:
java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
// L2-035 完全二叉树的层序遍历
public class Main {
static int[] postorder; // 后序遍历
static int[] tree = new int[31]; // 根据编号存储二叉树的节点
static int n;
public static void main(String[] args) throws Exception {
StreamTokenizer sr = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
sr.nextToken();
n = (int) sr.nval;
// 8
// 91 71 2 34 10 15 55 18
postorder = new int[n + 1];
for (int i = 1; i <= n; i++) {
sr.nextToken();
postorder[i] = (int) sr.nval;
}
// 18 34 55 71 2 10 15 91
initTree(1);
levelorder(1);
}
static int count = 1;
/**
* 从根节点开始根据后续遍历生成完全二叉树
*
* @param h
*/
private static void initTree(int x) {
if (x > n) {
return;
}
int left = x << 1; // 左节点在完全二叉树的序号
int right = (x << 1) + 1; // 右节点在完全二叉树的序号
initTree(left);
initTree(right);
tree[x] = postorder[count++];
}
/**
* 层序遍历
*
* @param x
*/
private static void levelorder(int x) {
String s = tree[1] + "";
for (int i = 2; i <= n; i++) {
s+=" " + tree[i];
}
System.out.print(s);
}
}

补充根据节点顺序数组,遍历二叉树
java
/**
* 前序遍历
*
* @param x
*/
private static void preorder(int x) {
if (x > n) {
return;
}
System.out.print(tree[x] + " ");
int left = x << 1; // 左节点在完全二叉树的序号
preorder(left);
int right = (x << 1) + 1; // 右节点在完全二叉树的序号
preorder(right);
}
/**
* 中序遍历
*
* @param x
*/
private static void inorder(int x) {
if (x > n) {
return;
}
int left = x << 1; // 左节点在完全二叉树的序号
inorder(left);
System.out.print(tree[x] + " ");
int right = (x << 1) + 1; // 右节点在完全二叉树的序号
inorder(right);
}
/**
* 后序遍历
*
* @param x
*/
private static void postorder(int x) {
if (x > n) {
return;
}
int left = x << 1; // 左节点在完全二叉树的序号
postorder(left);
int right = (x << 1) + 1; // 右节点在完全二叉树的序号
postorder(right);
System.out.print(tree[x] + " ");
}
评论
0 条—
还没有评论,来说第一句