3537. 树查找
给定一棵包含 nn 个结点(编号 1∼n1∼n)的完全二叉树的层序遍历序列,请按照从左到右的顺序输出该树第 kk 层的全部结点编号。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数,表示该二叉树的层序遍历序列。
第三行包含整数 kk。
输出格式
共一行,按照从左到右的顺序输出该树第 kk 层的全部结点编号。
数与数之间用单个空格隔开。
若无该层结点,则输出 EMPTY
。
数据范围
1≤n≤10001≤n≤1000,
1≤k≤201≤k≤20
输入样例:
4
1 2 3 4
2
输出样例:
2 3
题解(朴素做法)
import java.io.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int a[] = new int[1001];
int n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
int k = scanner.nextInt();
//预处理 每一层的高度
int mi[] = new int[21];
mi[0] = 1;
for (int i = 1; i < 21; i++) {
mi[i] = mi[i - 1] * 2;
}
//判断如果k是最后一层的话,起始位置到n+1
//int min = Math.min(mi[k],n+1);
if (n >= mi[k-1]) {
for (int i = mi[k-1]; i < mi[k] && i < n+1 ; i++) {
bw.write(a[i]+" ");
}
} else {
System.out.println("EMPTY");
}
bw.flush();
}
}
题解(优化)
import java.io.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int a[] = new int[1001];
int n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
int k = scanner.nextInt();
int r = (1 << k) - 2, l = r >> 1;
if (l >= n){
System.out.println("EMPTY");
} else {
for (int i = l; i <= r && i < n; i++) {
bw.write(a[i]+" ");
}
}
bw.flush();
}
}
评论区