题目是求二叉搜索树的最小公共父节点。首先想到的是能否采用递归的思想来处理？
采用递归的思想来处理的话，就要考虑p，q两节点的位置问题。如果二叉搜索树本身为NULL，则返回值就是NULL。若p和q至少有一个指向的是二叉搜索树的根节点，则返回值就是根节点。若p和q分别位于二叉搜索树的根节点的两侧，则返回值依旧是根节点。若p和q均位于二叉搜索树的左半边或者右半边，这个时候才是采用递归思想的时候了。
（1）C语言实现
/**
* 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) {
if(root == NULL)
return NULL;
if(p->val == root->val || q->val == root->val || (root->val - p->val)*(root->val - q->val)<0)
return root;
else if(p->val<root->val && q->val<root->val)
return lowestCommonAncestor(root->left, p,q);
else
return lowestCommonAncestor(root->right,p,q);
}
（2）C++语言实现
/**
* 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 == NULL)
return NULL;
if((p->val == root->val)||(q->val == root->val) || (root->val-p->val)*(root->val-q->val)<0)
return root;
else if((p->val < root->val) &&(q->val < root->val))
return lowestCommonAncestor(root->left, p, q);
else
return lowestCommonAncestor(root->right, p, q);
}
};
（3）java语言实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if(root.val == p.val || root.val == q.val || (root.val - p.val)*(root.val - q.val)<0)
return root;
else if(root.val>p.val && root.val>q.val)
return lowestCommonAncestor(root.left,p,q);
else
return lowestCommonAncestor(root.right,p,q);
}
}