首页 > 试题广场 >

二叉树

[编程题]二叉树

热度指数：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

输出

算法知识视频讲解

Java

任彦州

import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  while(in.hasNext()) {
   String []nn=in.nextLine().split(" ");
   int a=Integer.parseInt(nn[0]);
   int b=Integer.parseInt(nn[1]);
   while(true) {
    if(a==b) {
     break;
    }
    else if(a>b){
     a/=2;
    }
    else {
     b/=2;
    }
   }
   System.out.println(a);
  }
 }
}

发表于 2019-03-19 21:31:43 回复(0)

Java

/xinCupid☆

先判断两个节点是否在同一层，不是的话，让下面的节点往上走，直到在同一层。如果此时已经两个节点相等，直接返回结果。否则，让两个节点同时往上走，直到相遇。

简单做法当然就是直接让大数除2，直到相遇。

import java.util.*;
 
public class Main {
    public static double getLevel(int a)  {
        return Math.log(a)/Math.log(2);
    }
    
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            int x = reader.nextInt();
            int y = reader.nextInt();
            int levelx = (int)getLevel(x);
            int levely = (int)getLevel(y);
            while (levelx != levely) {
                if (levelx > levely) {
                    x /= 2;
                    levelx = (int)getLevel(x);
                } else {
                    y /= 2;
                    levely = (int)getLevel(y);
                }
            }
            while (x != y && x > 1 && y > 1) {
                x = x / 2;
                y = y / 2;
            }
            System.out.println(x);
        }
    }
}

编辑于 2018-04-28 18:27:20 回复(1)

Java

no_and_life

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            int n=input.nextInt();
            int m=input.nextInt();
            while(n!=m){
                n=n>m?n>>1:n;
                m=n<m?m>>1:m;
            }
            System.out.println(n);
        }
        input.close();
    }
}

编辑于 2018-04-12 16:48:10 回复(0)