235. Lowest Common Ancestor of a Binary Search Tree
235. Lowest Common Ancestor of a Binary Search Tree
🟠 🔖 树
深度优先搜索
二叉搜索树
二叉树
🔗 LeetCode
题目
Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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 )."
Example 1:
![](https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png)
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
![](https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png)
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1
Output: 2
Constraints:
- The number of nodes in the tree is in the range
[2, 105]
. -10^9 <= Node.val <= 10^9
- All
Node.val
are unique. p != q
p
andq
will exist in the BST.
题目大意
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
维基百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
解题思路
思路一:递归比数值
由于 BST 的性质,可以通过比较节点的值来确定最近的公共祖先。
- 如果节点的值小于 p 和 q 的值,说明 p 和 q 都在节点的右子树中,递归搜索右子树。
- 如果节点的值大于 p 和 q 的值,说明 p 和 q 都在节点的左子树中,递归搜索左子树。
- 如果节点的值在 p 和 q 的值之间,说明当前节点即为最近的公共祖先。
思路二:递归查找
和 第 236 题 一样,使用递归查找。
从根节点开始,递归地向左子树和右子树搜索。递归的终止条件有几种情况:
- 如果当前节点为
null
,表示遍历到空节点,直接返回null
。 - 如果当前节点等于
p
或q
,表示找到了其中一个节点,直接返回当前节点。
递归步骤如下:
- 递归地在左子树中寻找
p
和q
的最低共同祖先,结果存储在变量left
中。 - 递归地在右子树中寻找
p
和q
的最低共同祖先,结果存储在变量right
中。
然后,根据 left
和 right
的情况,可以得出以下结论:
- 如果
left
和right
都不为null
,说明p
和q
分别位于当前节点的左右子树,因此当前节点就是它们的最低共同祖先,直接返回当前节点。 - 如果只有
left
不为null
,说明p
和q
都在左子树,最低共同祖先在左子树中,返回left
。 - 如果只有
right
不为null
,说明p
和q
都在右子树,最低共同祖先在右子树中,返回right
。
代码
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (!root) return null;
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
} else if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
};
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (!root || p == root || q == root) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left ? left : right;
};
相关题目
- [236. 二叉树的最近公共祖先](./0236.md)
- [🔒 Smallest Common Region](https://leetcode.com/problems/smallest-common-region)
- [🔒 Lowest Common Ancestor of a Binary Tree II](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii)
- [🔒 Lowest Common Ancestor of a Binary Tree III](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii)
- [🔒 Lowest Common Ancestor of a Binary Tree IV](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv)