二元最近的共同祖先问题(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)


相关推荐

  • PYQT5 pycharm 编程环境和环境变量配置[通俗易懂]

    PYQT5 pycharm 编程环境和环境变量配置[通俗易懂]基本的环境配置

  • Channel9中关于Windows内核的采访录像

    Channel9中关于Windows内核的采访录像转载自http://advdbg.com/blogs/advdbg_system/articles/21.aspx今年一月份起,Channel9陆续访谈了一些微软内部的高级设计师和架构师,每次探讨Windows内核的一个方面。尽管录像和采访水准比.NetShow差很多,但是正因为采访的场合就在办公室,气氛也很随意,又很有针对性,因此谈的内容还是很值得一看的。建议大家茶余饭后边听边消遣一下。

  • Git的安装与使用教程(超详细!!!)「建议收藏」

    Git的安装与使用教程(超详细!!!)「建议收藏」git提交全部文件1、get.add.gitaddxx命令可以将xx文件添加到暂存区,如果有很多改动可以通过getadd-A.来一次添加所有改变的文件。注意-A选项后面还有一个句点。gitadd-A表示添加所有内容,gitadd.表示添加新文件和编辑过的文件不包括删除的文件;gitadd-u表示添加编辑或者删除的文件,不包括新添加的文件。2.、git…

  • chrome小恐龙源代码_chrome小恐龙代码

    chrome小恐龙源代码_chrome小恐龙代码Chrome小恐龙前端修改代码代码总结偶然间发现谷歌浏览器的离线小恐龙游戏,上网查找的攻略总结。Chrome小恐龙是什么?在Chrome(谷歌浏览器)断网之后访问在线页面,如a.com会出现以下

  • java jasypt_jasypt命令行工具的使用说明

    java jasypt_jasypt命令行工具的使用说明jasypt能够以很简单的方式为Java项目提供加密功能,这种简单的方式体现着它的命令行工具,与Spring,Hibernate,Springsecurity,wicket等第三方框架的集成。本文参加jasypt官方网站:http://www.jasypt.org/下载jasypt包,解压缩到本地目录。如下图:根目录:命令行工具目录:说明:在lib目录下是jasypt的核心jar和与第三方组件…

  • pycharm学生版更新license「建议收藏」

    pycharm学生版更新license「建议收藏」pycharm的学生license一年过期,需要更新license.看网上的po出的经验较少,即使有也有错误,前几天成功更新了,分享一下经验。1.首先登陆jetbrainshttps://www.jetbrains.com/zh-cn/2.使用学校邮箱登陆后查看license因为是前几天更新的所以这个截图是已经更新过的,如果是一年期license过期的话(就是validthrough日期已过),大概是红圈这个位置有一个绿色的“renew…”(具体内容不记得了)。3.点开后输入学校邮箱这时候

发表回复

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

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