北大百练题2756:
如上图所示,由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从10到根结点的路径是(10, 5, 2, 1),从4到根结点的路径是(4, 2, 1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1)。对于两个结点x和y,假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1, y2, ... ,1)(这里显然有x = x1,y = y1),那么必然存在两个正整数i和j,使得从xi 和 yj开始,有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,... 现在的问题就是,给定x和y,要求xi(也就是yj)。
输入
输入只有一行,包括两个正整数x和y,这两个正整数都不大于1000。
输出
输出只有一个正整数xi。
样例输入
10 4
样例输出
2
这个题目要求树上任意两个节点的最近公共父节点。分析这棵树的结构不难看出,
不论奇数偶数,每个数对 2 做整数除法,就走到它的上层结点。我们可以每次让较大的一个数(也就是在树上位于较低层次的节点)向上走一个结点,直到两个结点相遇。如果两个节点位于同一层,并且它们不相等,可以让其中任何一个先往上走,然后另一个再往上走,直到它们相遇。设 father(x, y)表示整数 x 和 y的最近公共子节点,那么,根据比较 x 和 y 的值,我们得到三种情况:
1) x 与 y 相等,则 father(x, y)等于 x 并且等于 y;
2)x 大于 y,则 father(x, y)等于 father(x/2, y);
3)x 大于 y,则 father(x, y)等于 father(x y/2);
AC代码:
import java.util.Scanner;
public class Main{
static int father(int x,int y){
if(x==y)
return x;
else if(x>y)
return father(x/2,y);
else
return father(x,y/2);
}
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int x=in.nextInt();
int y=in.nextInt();
System.out. println(father(x,y));
}
}
- 大小: 22.9 KB
分享到:
相关推荐
二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...
C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好
撰写一个程序,能够构建字符串型的二叉排序树并在二叉排序树中查找节点。 所谓二叉排序树,简而言之,是一个每个节点可指向 0、1 或 2 个节点的递归的数据结构。最上层的一个节点称为树根。二叉排序树服从凡是比...
1.在二叉搜索树中插入节点 2.前序、中序、后序遍历该二叉搜索树,写出遍历序列 3.输出二叉搜索树的深度、节点数目、叶子节点数目 4.退出
二叉排序树,也称为二叉查找树。... 现在给你N个关键字值各不相同的节点,要求你按顺序插入一个初始为空树的二叉排序树中,每次插入后成功后,求相应的父亲节点的关键字值,如果没有父亲节点,则输出-1
剑指 Offer II 056. 二叉搜索树中两个节点之和标签:树、深度优先搜索、广度优先搜索、二叉搜索树、哈希表、双指针、二叉树难度:简单题目大意给定一个二叉
1.在二叉搜索树中插入节点 2.前序、中序、后序遍历该二叉搜索树,写出遍历序列 3.输出二叉搜索树的深度、节点数目、叶子节点数目 4.退出
(6)求二叉排序树的所有节点数和叶子节点数; (7)向二叉排序树插入一条学生记录; (8)从二叉排序树中删除一条学生记录; (9)从二叉排序树中查询一条学生记录; (10)以广义表的形式输出二叉排序树 等功能。 ...
设计一个算法程序,使得该程序从二叉检索树中删除一个结点,并仍然保持二叉检索树的特性不变 实验要求: 创建一棵二叉检索树,然后用中序遍历查找要删除的结点的后继结点
解题思路明确一点即可:自己解题* 二叉搜索树中两个节点的最低公共祖先public class Solution {* 获得二叉搜索树中两个节点的最低公共祖先pu
。。。
。。。
二叉检索树c语言版,有一定量的注释,可以对我我写的C++版。
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
因为树的结构不同所以需要分情况...当树为二叉排序树,寻找给定两节点的最低公共祖先 当树为普通树,每个节点中有指针指向其父节点 当树为二叉树,每个节点仅有左右孩子指针 当树为普通树,每个节点仅有左右孩子指针
二叉查找树的最大最小以及任意数查找
使用二叉链表和c++来实现二叉搜索树,提供插入、删除、遍历、求最小节点、最大最节点等操作。
查找二叉排序树的双亲节点,并输出路径project
java基础面试题二叉搜索树的第k个节点本资源系百度网盘分享地址
剑指Offer(Python多种思路实现):二叉搜索树的第K大节点 面试54题: 题目:二叉搜索树的第K大节点 题:给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个...