题解 | #二叉树#

#include<iostream>
using namespace std;

/*
对于求根结点为m的树中有多少结点数目这个问题
可以将问题分解为求它左子树和右子树的结点数目这两个相同的子问题。
在得到其左、右子树的结点数目后，加上结点m本身便可得到问题的解。
当结点m>n时，
以m为根结点的树为空，那么该树的结点数目必定为0,
这个便是这个问题可被轻松求解的底层子问题，也是递归出口。
*/

int leftSub(int m) {
    return 2 * m;
}//求二叉树中左右子树的节点编号其实也是一种二级结论

int rightSub(int m) {
    return 2 * m + 1;
}

int CountNodes(int m, int n) {
    if (m > n) {
        return 0;
    }
    return 1 + CountNodes(leftSub(m), n) + CountNodes(rightSub(m), n);
}

int main() {
    int n, m;
    while (scanf("%d %d", &m, &n) != EOF) {
        printf("%d\n", CountNodes(m, n));
    }
}