https://www.cnblogs.com/grandyang/p/4641968.html
http://www.cnblogs.com/grandyang/p/4640572.html
利用二叉搜索树的性质：左子树所有节点小于根节点，右子树所有节点大于根节点
如果两个节点的最大值小于根节点，那最低公共祖先一定在左子树，去左子树找；
如果两个节点的最小值大于根节点，那最低公共祖先一定在右子树，去右子树找；
其他情况下，当前节点一定就是最低公共祖先。其中，其他情况包括两种，即p是q或者q是p的祖先 和 p、q拥有一个共同祖先，就是当前这个节点，这个节点刚好将p、q划分到两个子树。
1.这个题目还包含一种情况就是，p是q或者q是p的祖先。所以在比较的时候使用的是>和<，如果出现了等于，就直接返回这个值了，不再递归调用。
2.最低公共祖先如果将两个节点分在不同的子树中，在二叉搜索树中，最低公共祖先的值一定介于两个节点值之间。
235. Lowest Common Ancestor of a Binary Search Tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root)
return NULL;
if(root->val > max(p->val,q->val))
return lowestCommonAncestor(root->left,p,q);
if(root->val < min(p->val,q->val))
return lowestCommonAncestor(root->right,p,q);
else
return root;
}
};
依旧有两种情况：一个是p是q或者q是p的祖先，另一个是两个共用一个祖先
迭代返回的值只可能是NULL、p、q三种情况
如果left、right分别返回了p、q，那证明当前节点一定是最低公共祖先(因为是递归的，所以才是最低的，真正的返回值是在那个第一次获得left、right的节点返回的值)
这个题是直接搜索，就是判断节点是否等于我们需要寻找的两个节点
236. Lowest Common Ancestor of a Binary Tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left && right)
return root;
return left ? left : right;
}
};