1 问题描述

2 解题

• 这个题我其实想了很久，因为刚开始的时候我一直没有思路，觉得有太多的情况需要考虑，尤其是当第m层放不满的时候，如果要从右边拿过来的话就像是我们平时所说的牵一发而动全身，实在头疼
• 最后终于发现了其中的规律
• 首先从最简单的情况入手，先是每一层只放一个，然后来补嘛，
  
  然后开始往右填每一层，这个层已经不是横着的层了，但是其中还是有相同的规律
  
  当第4层无法填满的时候，把第四层当做一个新的开始，是不是自然而然想到递归了
  因为它回到了最开始的情况，情形处理都是一样的，不过这个时候传进去的参数m就不等于一开始的m了，应该是2
  
  递归结束的条件在程序里面都有写

• 代码：

#include <math.h> 
#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std;

int num=0;

void count(int n,int m){
	if(n<m+1){		//只放一个都不够
			num+=0;
			return;
	}
	else if(n==m+1){	//只放一个刚刚好
		num+=1;
		return ;
	}
	else{
		n=n-m-1;	//每层放一个之后剩下的
		num += 1;	///每层放一个那么m层就有1个了哦
		int layer=1;	//第0层已经有了，直接开始第1层吧

		if(n==0||layer>m)		//没有节点了，或者层数已经够了，结束递归
			return;
		int need;
		need=pow(2,layer)-1;		//放满需要的节点数
		
		while(n-need>0){	//只要能放满还剩，重复一直放
			num+=pow(2,layer-1);
			layer++;			
			n-=need;
			need=pow(2,layer)-1;
			if(layer>m)		//注意判断是否达到了退出的条件
				return ;
		}
		if(n-need==0){	//刚好放满
			num+=pow(2,layer-1);
			return;
		}	
		else			//新的一层不够放，那么当做一个新的情况开始递归吧
			count(n,layer-1);
				
	}
	
}
int main() {
    int n,m,t;
	//freopen("file in.txt","r",stdin);
	cin>>t;
	while(t--){
		cin>>n>>m;
		num=0;		//每一次都要初始化，不然会累加
		count(n,m);
		cout<<num<<endl;		
	}
	
    return 0;
}

3 小结

• 二叉树一般都有很强的规律性，只要能寻找到其中的规律，那么就可以使用递归，因为没有规律的话递归是没有办法连贯下去的