题解 | 二叉树

#include <iostream>
using namespace std;

int recursion(int m,int n){
    if(m>n)return 0;
    int s1 = recursion(m*2, n); //递归左子树
    int s2 = recursion(m*2+1, n); //递归右子树
    return s1+s2+1;
}


int main() {
    int m, n;
    while (cin >> m >> n) {
        if(m==0 && n==0 ){break;}
        int res = recursion(m,n);
        cout<<res;
    }
}
// 64 位输出请用 printf("%lld")

【解题思路】：递归，将大问题拆成和原问题相同的子问题；

【关键点】：

1. 在该二叉树中，左子树节点=父节点*2；右子树节点=左子树+1；
2. 递归出口是：当子节点m大于n时；此时m的孩子节点肯定是0，口返回0；