二元最近的共同祖先问题(O(n) time 而且,只有一次遍历,O(1) Space (它不考虑函数调用栈空间))

二元最近的共同祖先问题(O(n) time 而且,只有一次遍历,O(1) Space (它不考虑函数调用栈空间))

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

问题:

找到两个节点的二叉树的最近的共同祖先。

首先可以参考这个博客http://blog.csdn.net/cxllyg/article/details/7635992 ,写的比較具体,包含了节点包含父指针和不包含父指针的情况,还介绍了经典的Tarjan算法。

Tarjan算法非常精妙,可是使用了并查集,须要额外O(n)的存储空间。

上面博客中给的第三个方法也是须要记录根到节点的路径,须要O(log n)空间,当然考虑到普通情况下我们遍历树都是递归的方式。所以本身方法调用栈就是O(log n)空间占用率。 可是这是对于平衡的二叉树而言的。在最差情况下空间占用率还是O(n)。

所以。这里我给的算法不须要记录根到节点的路径。并且只遍历树一遍就能够完毕。

1. 首先深度遍历树,找到第一个节点,如果为p。这时设置两个节点的近期公共祖先为p

2. 继续深度遍历,找另外一个节点q, 如果这时找到q, 那么二者近期祖先就是p.

3. 否则,回退到上一层,这时二者的近期公共祖先也对应改成了p的父节点。由于以p为根的子树中没有发现另外一个节点q

4. 依此类推。找不到则继续回退到上一层,当找到q时,相应的二者近期公共祖先也就找到了。

5. 若是p==q,直接返回p作为近期公共祖先

6. 若二者不都存在于树中,则返回空。


public class CommonAncestor {

	public static void main(String[] args) {

		CommonAncestor ca=new CommonAncestor();
		TreeNode root=new TreeNode(0);
		TreeNode l1=new TreeNode(-1);
		TreeNode r1=new TreeNode(1);
		root.left=l1;
		root.right=r1;
		
		TreeNode l1l1=new TreeNode(-2);
		TreeNode l1r1=new TreeNode(-3);
		l1.left=l1l1;
		l1.right=l1r1;
		
		TreeNode r=ca.commonAncestor(root, l1, r1);
		System.out.println(r.val);
	}
	
	private TreeNode ancestor=null;
	private TreeNode firstFound=null;
	private boolean found=false;
	public CommonAncestor()
	{
		
	}
	
	public TreeNode commonAncestor(TreeNode root,TreeNode p,TreeNode q)
	{
		this.ancestor=null;
		this.found=false;
		findCommonAncestor(root,p,q);
		if(found)
			return ancestor;
		else
			return null;
	}

	private void findCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

		if(root==null)
			return ;
		if(found)
			return;
		this.findCommonAncestor(root.left, p, q);
		test(root,p,q);
		this.findCommonAncestor(root.right, p, q);
		test(root,p,q);
	}

	private void test(TreeNode root, TreeNode p, TreeNode q) {

		if(found)
			return;
		if(this.ancestor==null)
		{
			if(root==p)
			{
				this.ancestor=p;
				firstFound=p;
				if(p==q)
					found=true;
			}
			else if(root==q)
			{
				this.ancestor=q;
				firstFound=q;
				if(p==q)
					found=true;
			}
			
			
		}
		else
		{
			if(root.left==this.ancestor||root.right==this.ancestor)
			{
				this.ancestor=root;
			}
			if((root==p||root==q)&&root!=firstFound)
			{
				found=true;
			}
		}
	}

}


版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117080.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 高中物理学运动公式实现js动画

    高中物理学运动公式实现js动画js动画

    2022年10月15日
  • linux下如何保存退出vim编辑器

    linux下如何保存退出vim编辑器命令:vimapp.py如果不存在app.py则会自动创建1.进入编辑器后按字母“i”即可进入编辑状态(此时左下角会出现 “插入”)2.退出的时候分为4种情况:保存退出、正常退出、不保存退出以及强制退出 2.1:保存退出:按“Esc”键后此时的“插入”会消失,然后按Shift+zz就可以保存修改内容并退出 2.2:不保存退出:当修改修改了一部分内容后发现修改错了,此时就会进行不保存退…

  • MapReduce编程模型[通俗易懂]

    MapReduce编程模型[通俗易懂]1.MapReduce简介MapReduce是一个分布式运算程序的编程框架,核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序,并发运行在Hadoop集群上。一个完整的mapreduce程序在分布式运行时有三类实例进程:MRAppMaster负责整个程序的过程调度及状态协调MapTask负责map阶段的整个数据处理流程ReduceTask负责reduce阶段的整个数据处理流程2.MapReduce核心编程思想1)分布式的运算程序往往需要分成至少2个阶段。2

  • top 命令详解_top命令列含义

    top 命令详解_top命令列含义概况top命令是Linux下最常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。top命令1.命令格式:top[参数]2.命令功能:显示当前系统正在执行的进程的相关信息,包括进程ID、内存占用率、CPU占用率等3.命令参数:-b批处理-c显示完整的命令-I忽略失效过程-s保密模式-S

  • python 导入数据错误:UnicodeDecodeError: ‘utf-8’ codec can’t decode byte 0xb5 in position 0: invalid start

    python 导入数据错误:UnicodeDecodeError: ‘utf-8’ codec can’t decode byte 0xb5 in position 0: invalid start正想导入数据到python作分析找到这个教程https://www.cnblogs.com/OliverQin/p/8966321.html我要导入CSV文件,已经放在相同目录之下。importpandasaspddata=pd.read_csv("电信客户流失.csv",encoding="utf8")报错如下———————–…

  • 配置AAA认证和授权

    配置AAA认证和授权一、目的1、掌握AAA认证的工作原理。2、掌握使用CiscoSecureACS服务器实现AAA认证授权的方法。二、网络拓扑三、认证部分实验要求配置和测试本地和基于认证服务器的AAA认证。1、在R1上创建本地帐号,配置本地AAA认证登录console和VTY。2、配置和测试本地和基于认证服务器的AAA认证。1、在R1上创建本地帐号(用户名:A…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号