大体题意:
给你一棵二叉树,上面按层序遍历编好了号,给你两个节点,要求输出一系列点,这些点不能是这两个点的祖先,不要祖先,要祖先相邻的点,最后也要这两个点?
吐槽:
好坑啊,这就是一个大水题,当然要读懂题目(= =好弱!)
思路:
直接模拟走就可以了,都是log级别的相当于二分!
如果其中一个点是另一个点的祖先,那么肯定是-1了,
否则就模拟:
先把这两个点的祖先都存下来,最后模拟看那个点能要,哪个点不能要 用set比较方便!
详细见代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
set<int>s,check;
set<int>::iterator it;
int main(){
int a,b;
while(scanf("%d %d",&a,&b) == 2){
s.clear();
check.clear();
if (a > b)swap(a,b);
int t = b;
bool ok = 1;
while(t){
t /= 2;
if (t == a){
ok = 0;
break;
}
}
if (!ok){
printf("-1\n");
continue;
}
int ta = a, tb = b;
while(ta) { check.insert(ta/=2); }
while(tb) { check.insert(tb/=2); }
s.insert(a);
s.insert(b);
while(a > 1){
if (!check.count(a^1)) s.insert(a^1);
s.erase(a/=2);
}
while(b > 1){
if (!check.count(b^1)) s.insert(b^1);
s.erase(b/=2);
}
for (it = s.begin(); it != s.end(); ++it){
if (it != s.begin())printf(" ");
printf("%d",*it);
}
puts("");
}
return 0;
}