LeetCode: 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.

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).

给定一个二叉搜索树（BST），找到两个指定节点的最近公共祖先（LCA）。

最近公共祖先的定义是，在二叉树中，节点 p 和 q 的最近公共祖先是同时具有 p 和 q 作为后代的最低节点（允许一个节点是其自身的后代）。

Example

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.

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.

Solution

Approach: Recursive / 递归方法

In a Binary Search Tree (BST), the properties of the tree can be leveraged to efficiently find the Lowest Common Ancestor (LCA). Specifically:

If both p and q are smaller than the root, then the LCA lies in the left subtree.
If both p and q are greater than the root, then the LCA lies in the right subtree.
If p and q lie on either side of the root, the root is the LCA.

在二叉搜索树（BST）中，我们可以利用树的特性来高效地找到最近公共祖先（LCA）。具体来说：

如果 p 和 q 都小于根节点，那么 LCA 位于左子树。
如果 p 和 q 都大于根节点，那么 LCA 位于右子树。
如果 p 和 q 分别位于根节点的两侧，那么根节点就是 LCA。

Algorithm / 算法

Start at the root node.
If both p and q are smaller than the root, recursively search the left subtree.
If both p and q are greater than the root, recursively search the right subtree.
If p and q lie on either side of the root, return the root as the LCA.

Implementation / 实现

Python

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base condition
        if root is None:
            return None

        # If both p and q are smaller than root, LCA lies in left subtree
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        # If both p and q are greater than root, LCA lies in right subtree
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        # Otherwise, root is the LCA
        return root

Explanation

Base Condition / 基础条件
```
if root is None:
   return None
```
- English: If the tree is empty or the traversal reaches a leaf node, return None.
- Chinese: 如果树为空或遍历到叶节点，返回 None。
Check Left Subtree / 检查左子树
```
if p.val < root.val and q.val < root.val:
   return self.lowestCommonAncestor(root.left, p, q)
```
- English: If both p and q are smaller than the root, search for LCA in the left subtree.
- Chinese: 如果 p 和 q 都小于根节点，在左子树中寻找最近公共祖先。
Check Right Subtree / 检查右子树
```
if p.val > root.val and q.val > root.val:
   return self.lowestCommonAncestor(root.right, p, q)
```
- English: If both p and q are greater than the root, search for LCA in the right subtree.
- Chinese: 如果 p 和 q 都大于根节点，在右子树中寻找最近公共祖先。
Return Root as LCA / 返回根节点作为 LCA
```
return root
```
- English: If p and q lie on different sides of the root, then the root is the LCA.
- Chinese: 如果 p 和 q 位于根节点的两侧，那么根节点就是最近公共祖先。

Complexity Analysis

Time Complexity / 时间复杂度: O(h), where h is the height of the BST. In the worst case, we may traverse the entire height of the tree.
Space Complexity / 空间复杂度: O(h) due to the recursion stack.

Key Concept

Binary Search Tree Property / 二叉搜索树性质: Leverage the properties of BST to quickly locate the LCA by checking if the nodes are smaller or greater than the current root.

Summary

English: By using the properties of a Binary Search Tree, we can efficiently find the lowest common ancestor by recursively searching in the appropriate subtree or determining that the root is the LCA.
Chinese: 通过使用二叉搜索树的性质，我们可以通过递归地在适当的子树中查找，或者判断根节点就是最近公共祖先，从而高效地找到最近公共祖先。

Tips

English: In a Binary Search Tree, the LCA is determined based on the values of p and q compared to the root node.
Chinese: 在二叉搜索树中，最近公共祖先是基于 p 和 q 的值与根节点的比较来确定的。

Warning

English: This approach works only for Binary Search Trees. For generic binary trees, a different approach is needed.
Chinese: 此方法仅适用于二叉搜索树。对于普通二叉树，需要使用不同的方法。

5 More Similar Questions / 推荐5问题

Recommended Resources

English: Study how Binary Search Trees work, including their properties of ordering, to deepen your understanding of tree traversal and manipulation.
Chinese: 学习二叉搜索树的工作原理，包括它们的排序特性，以加深对树遍历和操作的理解。

Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python by Neetcode

Post Views: 11

CODEBITWAVE