lca_of_bst

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

意思就是找俩个节点的共同祖先。
这是一颗二叉搜索树，解决思路就比较简答。输入参数是根节点和找共同祖先的两个节点。我们就可以让两个节点和root节点做比较。有以下几种情况：

1. 两个节点中一个比根节点大，另一个比根节点小。那么他们的祖先就是root。
2. 两个节点有一个节点等于根节点，那么很显然他们的祖先就是root。
3. 两个节点都比root节点大，那么缩小两个几点的搜索范围，到root的右子树中，然后再和root->right 做比较。
4. 同理，两个节点都比root的节点小，到root的左子树做比较。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 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) ||(root->val < p->val && root->val> q->val))
            return root;
        if(root->val == p->val ||root->val== q->val)
            return root;
        if(root->val>p->val&&root->val>q->val)
            return lowestCommonAncestor(root->left,p,q);
        if(root->val<p->val&&root->val<q->val)
            return lowestCommonAncestor(root->right,p,q);
      
        
    }
};