思路1：对于一棵二叉排序树
1.如果当前节点的值小于p，q的值，那么LCA一定在root的右边；
2.如果当前节点的值大于p，q的值，那么LCA一定在root的左边；
3.如果当前节点的值在p，q的值之间，那么当前节点为LCA；
/**
* 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->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);
else return root;
}
};
思路2:直接搜索两个数p，q的值，记录下搜索过程的路径，左侧为-1，右侧为1.比对路径即可，路径开始不同的点即为LCA(即交叉点)
思路3：对于一棵二叉排序树，如果p，q均在当前节点左字树或者右子树，则根节点与p，q的值的差值同号，乘积大于零。
然后继续判断在左边还是在右边
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
while((root->val-p->val)*(root->val-q->val)>){
if(root->val-p->val>)
root=root->left;
else
root=root->right;
}
return root;
}