BT8 二叉搜索树最近公共祖先
约 854 字大约 3 分钟
2025-06-20
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
- 二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围: 3<=节点总数<=10000 0<=节点值<=10000
链接
示例
输入:{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值:7
说明:节点1 和 节点12的最近公共祖先是7
输入:{7,1,12,0,4,11,14,#,#,3,5},12,11
返回值:12
说明:因为一个节点也可以是它自己的祖先.所以输出12题解
知识点:二叉搜索树
二叉搜索树是一种特殊的二叉树,它的每个节点值大于它的左子节点,且大于全部左子树的节点值,小于它右子节点,且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。
思路:
二叉搜索树没有相同值的节点,因此分别从根节点往下利用二叉搜索树较大的数在右子树,较小的数在左子树,可以轻松找到p、q:
直接得到从根节点到两个目标节点的路径,这样我们利用路径就可以找到最近公共祖先。
具体做法:
step 1:根据二叉搜索树的性质,从根节点开始查找目标节点,当前节点比目标小则进入右子树,当前节点比目标大则进入左子树,直到找到目标节点。这个过程成用数组记录遇到的元素。
step 2:分别在搜索二叉树中找到p和q两个点,并记录各自的路径为数组。
step 3:同时遍历两个数组,比较元素值,最后一个相等的元素就是最近的公共祖先。
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param p int整型
* @param q int整型
* @return int整型
*/
function lowestCommonAncestor(root, p, q) {
// write code here
if (!root) return null;
// 先比较 p 和 q的大小
const [max, min] = p > q ? [p, q] : [q, p];
// min max root
// min root max
// min root/max
if (root.val > min) {
if (max >= root.val) {
// min root max : 那返回 root
// min root/max : 那返回 root
return root.val;
} else {
// min max root : 继续向下寻找
return lowestCommonAncestor(root.left, p, q);
}
}
// root min max
// root/min max
else {
// root/min max
if (root.val === min) {
return root.val;
} else {
// root min max: 向右下寻找
return lowestCommonAncestor(root.right, p, q);
}
}
}
module.exports = {
lowestCommonAncestor: lowestCommonAncestor,
};