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

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

https://www.programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

本题与二叉树的最近公共祖先不同之出,就是本题是二叉搜索树,可以利用二叉搜索树的有序性,如果val同时大于p q那么往左搜索,如果val同时小于p q那么往右边搜索,其他情况就只能是在p q之间了,那么这个节点就是他的最大祖先,直接返回。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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