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();
    }
}