Medium

题目描述

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

百科全书中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入: root = [2,1], p = 2, q = 1
输出: 2

提示:

  • 树中节点数目在范围 [2, 10^5] 内。
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同。
  • p != q
  • p 和 q 均存在于给定的二叉搜索树中。

解题思路

这道题利用二叉搜索树的性质可以很高效地解决。关键在于理解BST的特点：对于任意节点，左子树的所有值都小于该节点，右子树的所有值都大于该节点。

解法分析：

  1. 利用BST性质（推荐）：由于BST的有序性，我们可以通过比较当前节点值与p、q的大小关系来判断最近公共祖先的位置：

    • 如果p和q都小于当前节点值，说明LCA在左子树
    • 如果p和q都大于当前节点值，说明LCA在右子树
    • 否则当前节点就是LCA（p和q分布在当前节点两侧，或其中一个就是当前节点）

  2. 通用解法：不利用BST性质，采用递归遍历的方式，但时间复杂度较高。

实现方式：

  • 迭代实现：由于路径确定，可以用简单的while循环
  • 递归实现：代码更简洁，但有额外的函数调用开销

推荐使用迭代的BST性质解法，时间复杂度O(h)，其中h是树的高度，空间复杂度O(1)。

代码实现

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (p->val < root->val && q->val < root->val) {
                root = root->left;
            } else if (p->val > root->val && q->val > root->val) {
                root = root->right;
            } else {
                return root;
            }
        }
        return nullptr;
    }
};

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root
        return None

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

var lowestCommonAncestor = function(root, p, q) {
    while (root) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(h)，其中 h 是树的高度。最坏情况下为 O(n)
空间复杂度O(1)，只使用常数额外空间

相关题目