`
128kj
  • 浏览: 601709 次
  • 来自: ...
社区版块
存档分类
最新评论

求二叉树上任意两个节点的最近公共父节点

阅读更多


北大百练题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
分享到:
评论

相关推荐

    编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先.pdf

    编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先 本文将详细介绍如何编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先。该算法主要基于二叉排序树的特性,使用递归和迭代的方法来实现。 首先...

    编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先.docx

    总结起来,这个程序实现了在二叉排序树中查找两个节点最近公共祖先的功能。通过理解二叉排序树的性质和递归插入方法,我们可以有效地在树中定位和操作节点。在实际应用中,这种查找最近公共祖先的问题在数据结构和...

    二叉排序树删除 源代码

    这是因为这两个节点一定满足二叉排序树的性质,替换后依然保持树的有序性。 在C语言中,实现二叉排序树的删除操作通常包括以下步骤: 1. **搜索节点**:首先,需要遍历树以找到要删除的节点。这可以通过递归的中序...

    C#编写的二叉排序树

    二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键值,且对于任意节点,其左子树中的所有节点的键值都小于该节点的键值,右子树中的所有节点的键值都...

    常见的二叉树面试题大汇总(涵盖二叉搜索树)

    10. 二叉树的直径:找到树中最远两个节点之间的路径长度。 四、解题策略 1. 画图理解:对于复杂的二叉树问题,画出示意图有助于理解问题并找到解决方案。 2. 动态规划:对于涉及多步决策的问题,动态规划可以有效...

    一种高效二叉查找树---红黑树

    4. **红色节点的限制**:如果一个节点是红色的,则它的两个子节点必须都是黑色的(即不能出现红色节点相邻的情况)。 5. **黑色节点的数量**:对于任意节点,从该节点到达其每个叶子节点的所有路径上包含的黑色节点...

    算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树

    2. **二叉搜索树的最近公共祖先 (Lowest Common Ancestor of a Binary Search Tree)**:在二叉搜索树中找到两个给定节点的最近公共祖先。 3. **二叉树的最近公共祖先 (Lowest Common Ancestor of a Binary Tree)**:...

    数据结构C语言的二叉排序树

    二叉排序树(Binary Search Tree,BST),也称为二叉查找树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键值、一个指向左子树的指针和一个指向右子树的指针。在二叉排序树中,对于任意节点,其左子树中的...

    二叉排序树

    二叉排序树,又称二叉查找树或二叉排序树,是一种特殊的二叉树数据结构,它具有以下特性:对于树中的任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。...

    二叉排序树(数据结构实验 C语言实现 含报告文档)

    它具有以下特性:对于任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这个特性使得二叉排序树在插入、查找和删除操作上具有较高的效率。 在C语言中实现二叉...

    数据结构--查找--二叉排序树

    它具有以下特性:对于任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这个特性使得二叉排序树在插入、删除和查找操作上具有较高的效率。 1. **基本概念**: ...

    数据结构 二叉排序树PPT学习教案.pptx

    1. **定义**:在二叉排序树中,对于任意节点,其左子树上的所有节点的关键字都小于该节点的关键字,而右子树上的所有节点的关键字都大于该节点的关键字。 2. **查找算法**: - 查找过程从根节点开始。 - 如果给定...

    平衡二叉排序树PPT教案学习.pptx

    **LR型旋转**(左右旋转):如果一个节点的左子节点的右子节点插入新节点后失衡,需要进行两次旋转,先进行左子节点的右旋,再进行当前节点的左旋。 **RR型旋转**(右右旋转):与LL型旋转相反,当一个节点的右子...

    二叉搜索书的实现

    二叉搜索树(Binary Search Tree,BST)是一种特殊类型的二叉树,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉搜索树中,对于任意节点,其左子树中的所有...

    算法-树形结构- 树与二叉树- 无根树转有根树.rar

    二叉树是树的一个特殊形式,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树常用于实现搜索、排序等操作,如二叉搜索树和堆。 无根树与有根树的主要区别在于是否指定了一个特殊的节点作为树的根。...

    树结构,增 删除 经典

    习惯上规定只有一个根节点,没有父节点的节点称为根节点。除根节点外,其余每个节点有且仅有一个父节点,这样的结构被称为无环且有序的图。 2. **树的术语**: - 节点:树的基本构成单元,包含数据和指向子节点的...

    易语言二叉堆

    二叉堆是一种特殊的树形数据结构,它满足堆的特性:每个节点的值都大于或等于(最大堆)或小于或等于(最小堆)它的子节点。在易语言中实现二叉堆,可以帮助我们高效地执行一些操作,如查找最大或最小元素、插入元素...

    C# 二叉堆

    3. Dijkstra算法和Prim算法:这两个图论算法都需要在每一步找到当前未访问节点中的最小(或最大)权值,二叉堆可以有效地找到这个最小(或最大)值。 4. 调度算法:在任务调度、资源分配等领域,二叉堆可以帮助确定...

    VB基于二叉平衡搜索树实现的汉字转拼音源程序

    (2) 左子树上的所有节点的值小于父节点,右子树上的所有节点的值大于父节点。常见的平衡二叉搜索树有AVL树、红黑树等。在本例中,这种数据结构用于高效地存储和查找汉字与其拼音的映射关系。 汉字转拼音涉及到汉字...

Global site tag (gtag.js) - Google Analytics