1. Lowest Common Ancestor of a Binary Search Tree My Submissions QuestionEditorial Solution
   
   Total Accepted: 68335 Total Submissions: 181124 Difficulty: Easy
   
   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.

本题是BST，是二叉查找树

针对二叉查找树BST的情况

class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        assert(p!=NULL&&q!=NULL);

        if(root==NULL) return NULL;

        if(max(p->val, q->val) < root->val)

                return lowestCommonAncestor(root->left, p, q);

        else if(min(p->val, q->val) > root->val)

                return lowestCommonAncestor(root->right, p, q);

             else return root;

    }

};

针对一般的树有以下解决方法：

思路：

判定是否根，是的话返回根，不是

判定p,q的分布，如下：

/**

 * 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) {

        assert(p!=NULL&&q!=NULL); //默认p,q不为空，否则为空的不知归为哪个节点

        if(root==NULL)return NULL;

        if(root==p||root==q)return root;

        TreeNode *tmp;

        bool right_p=inTheTree(root->right,p),left_p = inTheTree(root->left,p);

        bool right_q=inTheTree(root->right,q),left_q = inTheTree(root->left,q);

        if((right_p&&left_q)||(right_q&&left_p))return root; //分别在左右子树，返回根

        if(right_p&&right_q)return lowestCommonAncestor(root->right,p,q);//全在右子树，转化为根为右节点的子问题

        if(left_p&&left_q)return lowestCommonAncestor(root->left,p,q);//全在左子树，转化为根为右节点的子问题

        return tmp;

    }

    bool inTheTree(TreeNode* head, TreeNode* p)//判定p是否在树中

    {

        if(head==NULL||p==NULL)return false;

        if(head==p)return true;

        else return inTheTree(head->left,p)||inTheTree(head->right,p);

    }

};