题目

二叉树结构如下：

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

题解

两个方法 这道题是236的子问题，多了二叉搜索树的限制。用236的方法也可以解决，但是就没有利用二叉搜索树的这个条件。
二叉搜索树有以下性质：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；
    利用这些性质，有迭代和递归两个方法，只要找到一个数在p和q之间就可以，比较简单，看代码吧

1. 迭代法

  • 时间复杂度 $O(N)$：其中N为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为logN（满二叉树），最大为N （退化为链表）。
  • 空间复杂度 $O(1)$：使用常数大小的额外空间。
class Solution {//两个方法。1.迭代
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root->val > p->val && root->val > q->val) root = root->left;
            else if(root->val < p->val && root->val < q->val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

2. 递归法

  • 时间复杂度 $O(N)$：其中N为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为logN（满二叉树），最大为N （退化为链表）。
  • 空间复杂度 $O(N)$：递归层数和二叉树的深度有关。
class Solution {//两个方法。2.递归
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val < p->val && root->val < q->val){
            return lowestCommonAncestor(root->right, p, q);
        }else if(root->val > p->val && root->val > q->val){
            return lowestCommonAncestor(root->left, p, q);
        } 
        return root;
    }
};