AcWing 3537. 树查找
原题链接
简单
作者:
曦薇
,
2022-07-04 10:22:00
,
所有人可见
,
阅读 212
思路
- 前序遍历一遍树,前序遍历本身同层结点就是从左到右的次序,所以只需要记录目标层次的结点,最后按序输出即可。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int tree[N];
vector<int> ans;
int n,d;
void pre(int node,int deep){
if(deep==d) ans.push_back(tree[node]);
if(node*2<=n) pre(node*2,deep+1);
if(node*2+1<=n) pre(node*2+1,deep+1);
}
int main(void){
int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&tree[i]);
}
scanf("%d",&d);
pre(1,1);
if(!ans.size()) cout<<"EMPTY"<<endl;
else{
for(i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}
return 0;
}