LeetCode 235. 二叉搜索树的最近公共祖先

Categories:

题目描述
思路分析
1. 解法一：迭代（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先

思路分析

解法一：迭代（推荐）

核心思路：

利用 BST 的有序性：左子树所有节点值 < 根节点值 < 右子树所有节点值。

从根节点出发，若 p、q 的值都小于当前节点，则 LCA 在左子树，向左走。

若 p、q 的值都大于当前节点，则 LCA 在右子树，向右走。

否则（p、q 分列当前节点两侧，或其中一个等于当前节点），当前节点即为 LCA。

迭代实现无需递归调用栈，空间复杂度 O(1)。

复杂度分析：

时间复杂度：O(h)，其中 h 为二叉搜索树的高度，平衡 BST 下 h = O(log n)，最坏情况退化为链表时 h = O(n)。

空间复杂度：O(1)，只使用了常数级别的额外空间。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 从根节点开始迭代查找
        while (root != null) {
            // p、q 都在左子树，向左走
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            // p、q 都在右子树，向右走
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                // p、q 分列两侧或当前节点即为 p 或 q，当前节点就是 LCA
                return root;
            }
        }
        return null;
    }
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 从根节点开始迭代查找
    for root != nil {
        // p、q 都在左子树，向左走
        if p.Val < root.Val && q.Val < root.Val {
            root = root.Left
        // p、q 都在右子树，向右走
        } else if p.Val > root.Val && q.Val > root.Val {
            root = root.Right
        } else {
            // p、q 分列两侧或当前节点即为 p 或 q，当前节点就是 LCA
            return root
        }
    }
    return nil
}

解法二：递归

核心思路：

与迭代思路完全一致，只是用递归形式表达。

若 p、q 都小于根节点值，则递归在左子树中查找。

若 p、q 都大于根节点值，则递归在右子树中查找。

否则当前节点即为 LCA，直接返回。

复杂度分析：

时间复杂度：O(h)，其中 h 为二叉搜索树的高度，平均情况 O(log n)，最坏情况 O(n)。

空间复杂度：O(h)，递归调用栈深度等于树的高度，平均 O(log n)，最坏 O(n)。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // p、q 都在左子树，向左递归
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // p、q 都在右子树，向右递归
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // 当前节点就是 LCA
        return root;
    }
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // p、q 都在左子树，向左递归
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    // p、q 都在右子树，向右递归
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    // 当前节点就是 LCA
    return root
}

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	DFS、后序遍历
1650. 二叉树的最近公共祖先 III	中等	指针上溯、链表相交思路
1676. 二叉树的最近公共祖先 IV	中等	DFS、多节点 LCA
701. 二叉搜索树中的插入操作	中等	BST 性质、递归
700. 二叉搜索树中的搜索	简单	BST 性质、递归
450. 删除二叉搜索树中的节点	中等	BST 性质、递归
98. 验证二叉搜索树	中等	BST 性质、DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/80298432