题目链接:235. 二叉搜索树的最近公共祖先
方法:利用二叉搜索树性质
解题思路
若两个节点值都大于或小于当前节点,那么其 \(LCA\) 一定在左右子树中,否则即为当前节点。
代码
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL;
int value = root->val;
if (p->val > value && q->val > value) return lowestCommonAncestor(root->right, p, q);
if (p->val < value && q->val < value) return lowestCommonAncestor(root->left, p, q);
return root;
}
};
复杂度分析
时间复杂度:\(O(n)\);
空间复杂度:\(O(1)\)。