当前位置: 首页 > article >正文

已知二叉树采用顺序存储,求编号为i和j的结点的最近公共祖先结点编号。

题目描述:已知二叉树采用顺序存储,求编号为 i和j的结点的最近公共祖先结点编号。

分析: 令两个下标从两个初始点开始,你追我赶的交替向上,直到在某地相遇。即先令较大的下标(对应位置较低的点)p通过p/2向上访问父节点——这是顺序存储树带来的最大方便——可以通过简单的计算得到父节点的位置——直到这个p超过了另一个下标,就令另一个下标开始往上访问。

 int Ancestor(int i,int j){
	while(i != j){
		if(i > j)
			i = i / 2;
		else if(j > i)
				j = k / 2;
			 else 
			 	return i;
	}
}

http://www.kler.cn/a/153245.html

相关文章:

  • 记一次:Python的学习笔记二(Django项目1)
  • Matlab数学建模算法详解之混合整数线性规划 (MILP) 算法(附完整实现代码)
  • mac如何永久设置环境变量
  • Java的53个关键字分类及详细说明(包含3个特殊直接量+2个保留字)
  • 大脑--学习方法
  • PG14归档失败解决办法archiver failed on wal_lsn
  • HTML5 的全局属性 hidden 和 display:none 的关系
  • 时间序列预测实战(二十)自研注意力机制Attention-LSTM进行多元预测(结果可视化,自研结构)
  • 开启新零售时代,引领消费革命
  • FPGA纯verilog实现 LZMA 数据压缩,提供工程源码和技术支持
  • 使用 Go 构建高性能的命令行工具
  • 麒麟linux将图片批量生成PDF的方法
  • Elasticsearch 的使用
  • CSS新手入门笔记整理:CSS表格样式
  • 海云安谢朝海:开发安全领域大模型新实践 人工智能助力高效安全左移
  • TZOJ 1429 小明A+B
  • 面试数据库八股文十问十答第一期
  • 修改git仓库地址
  • 回忆复习(Java语言概述一)
  • Java实现获取文件MD5值工具类