首页 > 试题广场 >

最近公共祖先

[编程题]最近公共祖先

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例：

2，3

返回：1

算法知识视频讲解

mythwind

发表于 2022-04-15 17:06:26

二叉树，通过图形来表示，可以快速获得父节点。 import java.util.*; public class LCA { public int getLCA(int a, int b) { // write code here while (a != b) 展开全文

阿贝尔的日记

发表于 2022-09-23 21:50:31

最近公共祖先最近公共祖先 /* 2022年09月21日 11:43:09 满二叉树 parent = child / 2 1 2 3 4 5 6 7 较大的数找父节点，两个数相等时，就是公共祖先 */ class LCA { public: int 展开全文

喜欢可抵岁月漫长

发表于 2023-07-03 20:50:32

import java.util.*; public class LCA { public int getLCA(int a, int b) { if(a==b){ return a; //节点相等的时候,返回其本身即可 }else{ 展开全文

喜欢后仰跳投的大魔王不愿再收感谢信

发表于 2023-07-20 23:12:01

class LCA { public: int getLCA(int a, int b) { if(a==b) return a; else if(a > b) a/=2; else 展开全文

硌手的小虫子

发表于 2023-04-05 14:43:15

import java.util.*; public class LCA { public int getLCA(int a, int b) { while (a!=b){ if(a>b){ a/=2; 展开全文

果粒陈33

发表于 2022-06-19 17:29:05

# -*- coding:utf-8 -*- class LCA: def getLCA(self, a, b): # write code here # 因为是按顺序排列的满二叉树，所以可以根据性质计算 while a != b: 展开全文

问题信息

动态规划递归

难度：

110条回答 118收藏 29412浏览

查看代码

最近公共祖先

扫一扫，把题目装进口袋