求出最左最右孩子:
从当前层(begin_level)遍历到最后一层(final_level),找到左右孩子left/right_side(有可能在此树中是不存在的);
计算从begin_level到final_level - 1层的满二叉树大小(2^(final_level-begin_level) - 1)
之后加上最后一层节点数:
if(left_side > n):说明子树是一颗从begin_level到final_level - 1的满二叉树;
else if(n <= right_side),要加上最后一层叶节点数量(即n-left_side+1);
else 是一颗从begin_level到final_level的满二叉树;
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
//判断结点x在树的第几层(从第1层开始),第i层最后一个节点编号为2^i - 1
//第i层结点编号为2^(i-1) ~ 2^i-1
int fc(int x){
for(int i = 1;;i++){
if(x <= pow(2,i) - 1){
return i;
}
}
return 0;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int m,n;
while(1){
cin>>m>>n;
if(m == 0 && n == 0) return 0;
int begin_level = fc(m);//m在第几层
int final_level = fc(n);//n在第几层(此树的最后一层)
//找到以m为根的子树在final_level层中的最左&最右孩子编号
//可能在此树中不存在
int left_side = m;
int right_side = m;
for(int i = begin_level;i < final_level;i++){
left_side *= 2;
right_side = right_side * 2 + 1;
}
//计算begin_level ~ final_level-1层的满二叉树大小
int res = pow(2,final_level - 1 - begin_level + 1) - 1;
//三种情况
if(n < left_side){//说明最左孩子不存在
}else if(n <= right_side){//最右孩子不存在
res += (n - left_side + 1);
}else{//都存在
res += (right_side - left_side + 1);
}
cout<<res<<endl;
}
return 0;
}
法二:队列层序遍历,超时
#include<iostream>
#include<queue>
using namespace std;
int main(){
int m,n;
while(1){
cin>>m>>n;
if(m == 0 && n == 0) return 0;
int res = 1;
queue<int> q;
q.push(m);
while(!q.empty()){
int t = q.front();
q.pop();
if(t * 2 <= n){
res++;
q.push(t * 2);
}
if(t * 2 + 1 <= n){
res++;
q.push(t * 2 + 1);
}
}
cout<<res<<endl;
}
return 0;
}