235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最低公共祖先（难）

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

[思路]

如果如果p,q 比root小, 则LCA必定在左子树, 如果p,q比root大, 则LCA必定在右子树. 如果一大一小, 则root即为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==NULL || p==NULL || q==NULL){
            return NULL;
        }
        if(root->val>p->val && root->val>q->val){
            return lowestCommonAncestor(root->left,p,q);
        }else if(root->val<p->val && root->val<q->val){
            return lowestCommonAncestor(root->right,p,q);
        }else{
            return root;
        }
    }
};

参考

http://blog.csdn.net/xudli/article/details/46838747