首页 > 试题广场 >

二叉树

[编程题]二叉树

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

      1
      / \
    2   3
    / \ / \
  4 5 6 7
  /\ /\ /\ /\
如上图所示，由正整数 1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从5到根结点的路径是（5, 2, 1），从4到根结点的路径是（4, 2, 1），从根结点1到根结点的路径上只包含一个结点1，因此路径就是（1）。对于两个结点x和y，假设他们到根结点的路径分别是（x1, x2, ... ,1）和（y1, y2,...,1），那么必然存在两个正整数i和j，使得从xi 和yj 开始，有xi = yj，xi + 1 = yj + 1，xi + 2 = yj + 2，...
现在的问题就是，给定x和y，要求他们的公共父节点，即xi（也就是 yj）。

输入描述:

输入包含多组数据，每组数据包含两个正整数x和y（1≤x, y≤2^31-1）。

输出描述:

对应每一组数据，输出一个正整数xi，即它们的首个公共父节点。

示例1

输入

10 4

输出

算法知识视频讲解

Python

lx的流星

while True:
    try:
        inp1,inp2=map(int,input().strip().split(' '))
        def root(i):
            list1=[]
            while i!=1:
                list1.append(i)
                i=i//2
            list1.append(i)
            return list1
        min_num=min(inp1,inp2)
        max_num=max(inp1,inp2)
        root_list1=root(min_num)
        root_list2=root(max_num)
        for i in root_list1:
            if i in root_list2:
                print(i)
                break
    except:
        break

发表于 2019-08-21 13:22:10 回复(0)

Python

TimeMac

try:
    while True:
        a,b = list(map(int,input().split()))
        while a != b:
            if a < b:
                b //= 2
            else:
                a //= 2
        print(a)
except Exception:
    pass

编辑于 2018-10-08 15:32:34 回复(0)