题解 | #在二叉树中找到两个节点的最近公共祖先#

/**
**方法判断一个树基本结构上有没有需要找的数，list存放节点；利用递归找出所有节点
*/

public static boolean getPathToNode(TreeNode root, int node, List<integer> path){
if (root.val==node){
return true;
}
if (root.treeLeft!=null){
path.add(root.treeLeft.val);
if (getPathToNode(root.treeLeft,node,path)){
return true;
}else {
path.remove(path.size()-1);
}
}
if (root.treeRight!=null){
path.add(root.treeRight.val);
if (getPathToNode(root.treeRight,node,path)){
return true;
}else {
path.remove(path.size()-1);
}
}
return false;
}
/**
**两个list里面所有相同的值最后一个就是需要找的公共祖先
*/
public static int lowestCommonAncestor(TreeNode root,int o1,int o2){
List<integer> pathOne=new ArrayList<>();
List<integer> pathTwo=new ArrayList<>();
pathOne.add(root.val);
pathTwo.add(root.val);
getPathToNode(root,o1,pathOne);
getPathToNode(root,o2,pathTwo);
int res=0;
for (int i = 0; i < pathOne.size()&&i<pathTwo.size(); i++) {
if (pathOne.get(i)==pathTwo.get(i)){
res= pathOne.get(i);
}else {
break;
}
}
return res;
}</integer></integer></integer>