注意二叉搜索樹與二叉樹的區(qū)別，左<根<右

//(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
版權聲明：本文為博主原創(chuàng)文章，轉載請附上博文鏈接！

//(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);
    }
};