九度OJ-1113-二叉树

本文主要是介绍九度OJ-1113-二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做本题的时候，第一次用思路最简单但是时空复杂度较差的递归去遍历其子树，结果TLE。于是乎只能改用数学计算的方法，去逐层累加。

故本题实际上考察点是：完全二叉树节点个数的计算

题目地址：点击打开链接

题目描述：

 

    如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

    比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。

输入：

    输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。

输出：

    对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

样例输入：

3 120 0

样例输出：

4

来源：

2007年北京大学计算机研究生机试真题

答疑：

解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-7836-1-1.html

#include <iostream>
#include <cmath>
using namespace std;int main(){int m,n;int level,count;while (cin>>m>>n,m||n){//initiatecount=0;//processfor (level=1;m*pow(2,level-1)<=n;level++);level-=1;		//level为此子树的层数 if (n>(m+1)*pow(2,level-1)-1){//若n在子树外count=pow(2,level)-1;} else //若n在子树中 count=(n-m*pow(2,level-1)+1)+(pow(2,level-1)-1);//最后一层的节点数+除去最后层的树的节点数 //outputcout<<count<<endl; }return true;
} 

这篇关于九度OJ-1113-二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---