题解 | #二叉搜索树的最近公共祖先#

W
按照图中的来进行递归，流程是遇到所需节点就立马返回，这样就得到所需要的节点
后序查看返回值，根据返回值的情况来判断是那种情况，如果不是由要找的节点返回来，那么就是从叶子节点返回来的
N
判断后序节点是否为空，都为空需要返回空

由于该题为二叉搜索树，所以可以直接递归
判断当前节点是在区间的左边还是右边，左边返回left,右边返回right,如果是中间直接返回即可，注意如果是要找的节点也需要返回
如下图所示寻找0和3的公共祖先，那么7大于二者，就需要往左子树寻找，然后到1，正好在二者中间，返回判断不为空，那么公共祖先为1这个节点

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    TreeNode* Tra(TreeNode* root,int p,int q){
        if(root == nullptr){
            return nullptr;
        }
        if(root->val==p || root->val==q){
            return root;
        }
        TreeNode* left=Tra(root->left,p,q);
        TreeNode* right=Tra(root->right,p,q);
        if(left && right) return root;//note 返回节点
        else if(left!= nullptr && !right){//右为空，左有值
            return left;
        }
       else if(right!=nullptr && !left){
            return right;
        }
        else //都为空 note
        return nullptr;
    }
    TreeNode* Tra_search(TreeNode* root,int p,int q)
    {
        if(root==nullptr) return root;
        //二叉搜索树
        if(root->val > p && root->val >q) //find in left tree
        {
            TreeNode* left=Tra_search(root->left,p,q);
            if(left!=nullptr){
                return left;
            }
        }
        if(root->val < p && root->val <q) //find in left tree
        {
            TreeNode* right=Tra_search(root->right,p,q);
            if(right!=nullptr){
                return right;
            }
        }
        return root;//在两者中间，或者就是要找的节点
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        TreeNode* res=Tra_search(root,p,q);//Tra(root,p,q);
        if(!res)
            return -1;
        return res->val;
    }
};