首页 > 试题广场 >

二叉树

[编程题]二叉树

热度指数：16032 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

如上所示，由正整数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)。

输出描述:

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

示例1

输入

3 12
0 0

输出

算法知识视频讲解

Python

lx的流星

while True:
    try:
        m,n=map(int,input().strip().split(' '))
        #print(m,n)
        re=m
        list1=[]
        def tree(i):
            if i>n:
                return list1
            else:
                list1.append(i)
                tree(2*i)
                tree(2*i+1)
        tree(m)
        #print(list1)
        print(len(list1))
    except:
        break

递归比较好想到，但是太慢了

编辑于 2019-07-31 23:06:44 回复(0)

Python

TimeMac

不用递归，耗时。同一颗树来说，从当前层开始，记录最左节点数（左结点是上一层最左结点*2）最右结点（右结点是上一层最右结点*2+1）。如果最右结点>=总结点数，结束。

而二叉树的结点数是每层是上一层的两倍。

最后一层要处理。如果左结点未超总结点数，则把剩余的加上。

while True:
    try:
        i,num = list(map(int,input().split()))
        result,level = 1,1
        leftNode,rightNode = 2*i,2*i+1
        while rightNode <= num:
            level *= 2
            result += level
            leftNode *= 2
            rightNode = rightNode*2 + 1
        if leftNode <= num:
            result += num-leftNode+1
        print(result)
    except Exception:
        break

编辑于 2018-09-29 20:44:23 回复(0)