02788: 二叉树（2）

http://cs101.openjudge.cn/practice/02788/

如上图所示，由正整数1，2，3……组成了一颗二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

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

输入

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。

输出

对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

样例输入

3 12
0 0

样例输出

利用每层节点的编号区间来计算子树中存在的节点数量。这样既能保证效率，也能避免超时问题：

python

import sys

def count_subtree_nodes(m, n):
    count = 0
    left = m
    right = m
    # 每层的节点编号范围为 [left, right]
    while left <= n:
        count += min(n, right) - left + 1
        left *= 2
        right = right * 2 + 1
    return count

def main():
    input_stream = sys.stdin
    for line in input_stream:
        m, n = map(int, line.split())
        if m == 0 and n == 0:
            break
        print(count_subtree_nodes(m, n))

if __name__ == '__main__':
    main()

说明

每层计算：
- 对于子树中每一层，节点编号的区间为 [left, right]，其中初始 left = m 和 right = m。
- 下一层的区间为 [left*2, right*2+1]。
节点数计算：
- 对于每一层，实际存在的节点数为 min(n, right) - left + 1，确保不超过 n。

这种方法的时间复杂度约为 O(log n)，能高效解决问题，并且避免了内存和时间上的超限问题。

完全二叉树
每个结点
左孩子 2*i 右孩子 2*i+1

设置left right 按照完全二叉树每一行去遍历算就行，算最左结点、最右结点.

python

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break

    ans = 1
    num = 1  # Number of nodes in the first level of the complete binary tree
    left = 2 * m
    right = 2 * m + 1
    while right <= n:
        num = num * 2
        ans += num
        left = left * 2
        right = right * 2 + 1

    if left <= n:
        ans += n - left + 1

    print(ans)

python

import sys

def count_subtree_nodes(m, n):
    left_bound, right_bound, depth = 2 * m, 2 * m + 1, 1

    while left_bound <= n:
        if right_bound < n:
            depth += 1
            left_bound *= 2
            right_bound = 2 * right_bound + 1
        else:
            return (1 << depth) + (n - left_bound)

    return (1 << depth) - 1

def main():
    input_data = sys.stdin.read().strip().split("\n")
    for line in input_data:
        m, n = map(int, line.split())
        if m == 0 and n == 0:
            break
        print(count_subtree_nodes(m, n))

if __name__ == "__main__":
    main()

python

#23n2300010763
def compute(m,n):
    cnt = 1
    while m*cnt<=n:
        cnt *= 2
    return min(n-(m-1)*(cnt//2),cnt-1)


while True:
    m,n = map(int,input().split())
    if not m and not n:
        break
    print(compute(m,n))

c++

#include<iostream>
using namespace std;

int main()
{
    int m,n,sum;
    while(scanf("%d%d",&m,&n)==2 && (m||n)) {
        sum=0;
        int d=1;
        while(1) {
            if(m<=n) {
                sum+=d;
                m=2*m+1;
                d=d*2;  
            }
            else{ 
                if(m-n<d)
                    sum = sum+d-(m-n);
                break;
            }
        }

        printf("%d\n",sum);
    }
}

02788: 二叉树（2） ​

02788: 二叉树（2）