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

/**
 * 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整型
     */
    int max(int a, int b){
        return a>b?a:b;
    }
    int min(int a, int b){
        return a<b?a:b;
    }
    //这题和找到二叉树的最近公共祖先最大的区别就是，二叉树是无序的，二叉搜索树是有序的
    //所以每一次我们都知道应该往哪走能找到最近公共祖先
    //可以发现如果一个节点的值在[p,q]之间（假设p<q）那么这个节点就是我们想要的
    //所以当遍历到某一个节点时，如果这个节点比p，q的最大值还要大时，就说明要往左孩子移动，反之往右边移动
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(root==NULL)
            return -1;
        TreeNode*cur=root;
        while(cur){//当节点不为空时
            if((cur->val>=p&&cur->val<=q)||(cur->val>=q&&cur->val<=p)){//因为不知道pq谁更大时所以要分情况
                //此时说明已经找到最近公共祖先节点了
                return cur->val;
            }
            else if(cur->val<min(p, q)){//此时要往右移动
                cur=cur->right;
            }
            else 
                cur=cur->left;
        }
        //如果循环结束都没有找到最近公共祖先节点说明没有返回-1
        return -1;
    }
};