题解 | 二叉树 nan

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;

int main() {
	int n, m;
	
		scanf("%d%d", &m, &n);  // 根 结点最大值
		

		int i = 1; // 获取层数
		int begin_level;  // 存储子树的根在第几层
		int final_level;  // 大树总共有几层
		// 2^(i-1) - 2^i-1
		// 1<<i ==> 2^i
		while (1) {
			if (m >= 1 << (i - 1) && m < 1 << i) {
				begin_level = i;
			}
			if (n >= 1 << (i - 1) && n < 1 << i) {
				final_level = i;
				break;
			}
			i++;
		}


		// 找m的最左/最右孩子结点编号
		int left_side = m;
		int right_side = m;
		for (i = begin_level; i < final_level;i++) {
			left_side = 2 * left_side;
			right_side = 2 * right_side + 1;
		}

		int treeNum;
		// left_side > n  说明 实际的最左、最有孩子在倒数第2层
		// 子树是一颗 从begin_level - final_level-1 满二叉树
		if (left_side > n) {
			treeNum = (1 << (final_level - begin_level)) - 1;
		}
		else if(n <= right_side) {
			treeNum = (1 << (final_level - begin_level)) - 1;
			treeNum += n - left_side + 1;
		}
		else {
			treeNum = (1 << (final_level - begin_level + 1)) - 1;
		}
		printf("%d\n",treeNum);
	
	return 0;
}