友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodesand28 is6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodesand24 is2, since a node can be a descendant of itself according to the LCA definition.
Note:
-
All of the nodes' values will be unique.
-
p and q are different and both values will exist in the BST.
思路分析
要充分利用二叉搜索树的特性：左大右小，如果根节点大于两个指定节点的值，那么公共祖先就在左子树上；如果根节点小于两个指定节点的值，那么公共祖先就在右子树上；否则就是他们的公共祖先节点。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 要充分利用二叉搜索树的特性
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-24 18:21:20
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode result = root;
while (result != null) {
if (p.val < result.val && q.val < result.val) {
root = root.left;
} else if (p.val > result.val && q.val > result.val) {
result = result.right;
} else {
break;
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-18 22:02:24
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if ((p.val <= root.val && root.val <= q.val)
|| (q.val <= root.val && root.val <= p.val)) {
return root;
} else if (p.val <= root.val && q.val <= root.val) {
return lowestCommonAncestor(root.left, p, q);
} else {
return lowestCommonAncestor(root.right, p, q);
}
}
作为这道题的延伸，继续看 236. Lowest Common Ancestor of a Binary Tree。
参考资料
-
235. 二叉搜索树的最近公共祖先 - 3种解决方式 — 根节点与两个节点的差值相乘，如果小于
0则节点分布在左右子树上，当前根节点就是公共祖先节点。