大家好,又见面了,我是全栈君,今天给大家准备了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账号...