题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000
示例
以下两例的示例图都是这个
image.png
- 示例1
输入：{7,1,12,0,4,11,14,#,#,3,5},1,12
输出：7
说明：节点1 和 节点12的最近公共祖先是7
- 示例2
输入：{7,1,12,0,4,11,14,#,#,3,5},12,11
输出：12
说明：因为一个节点也可以是它自己的祖先.所以输出12
思路
二叉搜索树没有相同的节点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q。
//节点值都不同，可以直接用值比较
while(node.val != target) {
path.add(node.val);
//小的在左子树
if(target < node.val)
node = node.left;
//大的在右子树
else
node = node.right;
}
步骤：
- 根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，知道找到目标节点。这个过程用数组记录遇到的元素。
- 分别在搜索树中找到p和q两个点，并记录各自的路径为数组。
- 同时便利两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。
代码实现
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
//收集到target的路径
public ArrayList<Integer> getPath(TreeNode root,int target){
ArrayList<Integer> path = new ArrayList<Integer>();
TreeNode node = root;
while(node.val != target){
path.add(node.val);
if(target<node.val){
node = node.left;
}else{
node = node.right;
}
}
path.add(node.val);
return path;
}
public int lowestCommonAncestor (TreeNode root, int p, int q) {
//记录路径
ArrayList<Integer> p_path = getPath(root,p);
ArrayList<Integer> q_path = getPath(root,q);
int res = 0;
for(int i = 0; i < p_path.size() && i < q_path.size(); i++){
int x = p_path.get(i);
int y = q_path.get(i);
//最后一个相同的节点就是最近公共祖先
if(x == y)
res = x;
else
break;
}
return res;
}
}
通知
小编最近可能要转战Hexo搭建自己的博客，Hexo搭建起来的博客不仅界面舒服，而且可以轻松地根据标签和分类查看想看的内容，并且每篇文章还能根据旁边的目录定位到对应位置。
小编已经搭建的差不多了，如果准备好了会在简书中放地址。
