本文共 1349 字，大约阅读时间需要 4 分钟。

情况1：

二叉树是个二叉查找树，且root和两个节点的值(a, b)已知。

如果该二叉树是二叉查找树，那么求解LCA十分简单。

基本思想为：从树根开始，该节点的值为t，

如果t大于t1和t2，说明t1和t2都位于t的左侧，所以它们的共同祖先必定在t的左子树中，从t.left开始搜索；

如果t小于t1和t2，说明t1和t2都位于t的右侧，那么从t.right开始搜索；

如果t1<=t<= t2，说明t1和t2位于t的两侧（或t=t1，或t=t2），那么该节点t为公共祖先。

public static TreeNode getLCA1(TreeNode root,int a,int b)	{			while(root!=null)		{			if(root.val > a && root.val > b){				root=root.left;			}else if(root.val < a && root.val < b){				root=root.right;			}else				return root;		}		return null;	}

情况2：

普通二叉树，root未知，但是每个节点都有parent指针。

基本思想：分别从给定的两个节点出发上溯到根节点，形成两条相交的链表，问题转化为求这两个相交链表的第一个交点，即传统方法：求出linkedList A的长度lengthA， linkedList B的长度LengthB。然后让长的那个链表走过abs(lengthA-lengthB)步之后，齐头并进，就能解决了。

有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。

二叉树节点是按顺序编号，所以 父节点=子节点/2

package test;import java.util.Scanner;/** * @author xxh 	* @date 创建时间：Aug 22, 2017 3:24:03 PM  */public class LCA {	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		int a = sc.nextInt();		int b = sc.nextInt();		System.out.println(getLCA(a,b));	}	public static int getLCA(int a, int b) {		// TODO Auto-generated method stub		int depthA=getDepth(a);		int depthB=getDepth(b);		if(depthA>depthB)		{			while(depthA-depthB!=0)			{				a=a/2;				depthA--;			}		}		if(depthA

Tarjan(离线)算法（基于并查集和深度优先搜索dfs )

参考http://www.cnblogs.com/JVxie/p/4854719.html