LeetCode 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

• Categories:

• Tags:

1. 题目描述
2. 思路分析
   1. 解法一：利用 BST 性质（推荐）
3. 相似题目

题目描述

✅ 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

思路分析

解法一：利用 BST 性质（推荐）

核心思路：

• 若 p、q 均小于当前节点，则 LCA 在左子树。
• 若 p、q 均大于当前节点，则 LCA 在右子树。
• 否则当前节点就是最近公共祖先。

复杂度分析：

• 时间复杂度：O(h)，其中 h 表示树高。
• 空间复杂度：O(1) 额外空间。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
}

func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
	cur := root
	for cur != nil {
		if p.Val < cur.Val && q.Val < cur.Val {
			cur = cur.Left
		} else if p.Val > cur.Val && q.Val > cur.Val {
			cur = cur.Right
		} else {
			return cur
		}
	}
	return nil
}

相似题目

题目	难度	考察点
235. 二叉搜索树的最近公共祖先	简单	BST
236. 二叉树的最近公共祖先	中等	树递归
98. 验证二叉搜索树	中等	BST
701. 二叉搜索树中的插入操作	中等	BST
530. 二叉搜索树的最小绝对差	简单	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/23594065

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！