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

注意二叉搜索树与二叉树的区别，左<根<右

//(1)二叉树
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root==NULL||p==root||q==root)
                return root;
            if(inTree(root->left,p))
            {
                if(inTree(root->right,q))
                    return root;
                return lowestCommonAncestor(root->left,p,q);//递归
            }
            else
            {
                if(inTree(root->left,q))
                    return root;
                return lowestCommonAncestor(root->right,p,q);
            }
        
    }
private:
    bool inTree(TreeNode* root,TreeNode* t)//判断t在不在该树
    {
        if(root==NULL)
            return false;
        if(root==t)
            return true;
        bool found=inTree(root->left,t);
        if(!found)
            found=inTree(root->right,t);
        return found;
    }
};

以下是参考他人的
作者：ColiYin
来源：CSDN
原文：https://blog.csdn.net/sinat_20177327/article/details/80046714
版权声明：本文为博主原创文章，转载请附上博文链接！

//(2)二叉搜索树  
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || root == p || root == q)
            return root;

        if ((root->val > p->val && root->val < q->val) ||    //p和q在root的左右两边
         root->val < p->val && root->val > q->val)
            return root;

        if (p->val < root->val && q->val < root->val)    // p和q都小于root，则结果在左边
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};