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

#include <stack>
class Solution {
public:
//思路：该树节点的值比pq都小，说明pq都在右子树，比pq都大，说明pq都在左子树，处于pq之间，说明正好一左一右，该节点就是最近公共祖先。
//另外，这题也可以用题解中的路径法来做。
    int solve(TreeNode* root,int p,int q)
    {
        if(root==nullptr)
            return -1;
        int val=root->val;
        if(val==p || val==q)
        {
            return val;
        }
        if(val > p && val<q)
        {
            return val;
        }
        if(val<p && val<q && root->right)
            return solve(root->right, p, q);
        if(val>p && val>q && root->left)
            return solve(root->left, p, q);
        return -1;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        return solve(root, p, q);
    }
};