题解 | 二叉树

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

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

// 输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。

//对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
int main() {
    int n, m;
    scanf("%d %d", &m, &n);
    int level_n, level_m;
    int i = 1;
    while (true) { //获得m, n的层数
        if (m > (1 << i - 1) && m < (1 << i)) {
            level_m = i;
        }
        if (n > (1 << i - 1) && n < (1 << i)) {
            level_n = i;
            break;
        }
        i++;
    }
    int left_side = m, right_side = m;
    for (int i = 0; i < level_n - level_m; i++) {
        left_side = left_side * 2;
        right_side = right_side * 2 + 1;
    }
    int NodeNum;
    if (left_side > n) {
        NodeNum = (1 << level_n - level_m) - 1;
    } else if (right_side >= n) {
        NodeNum = (1 << level_n - level_m) - 1;
        NodeNum += n - left_side + 1;
    } else {
        NodeNum = (1 << level_n - level_m + 1) - 1;
    }
    printf("%d\n", NodeNum);
    return 0;
}