大家好，又见面了，我是全栈君。
问题：
找到两个节点的二叉树的最近的共同祖先。
首先可以参考这个博客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. 若二者不都存在于树中，则返回空。
代码语言：javascript复制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;
}
}
}
}版权声明：本文博主原创文章。博客，未经同意不得转载。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117080.html原文链接：https://javaforall.cn
