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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param p int整型
 * @param q int整型
 * @return int整型
 */

int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    struct TreeNode* cur = root;
    int temp = 0;
    //将p指向较小的值，q指向较大的值
    if (q < p ) {
        temp = p;
        p = q;
        q = temp;
    }
    while (1) {
        //p为最近公共祖先
        if (cur->val == p)
            return p;
        //q为最近公共祖先
        else if (cur->val == q)
            return q;
        //cur所指结点为最近公共祖先
        else if (cur->val > p && cur->val < q)
            return cur->val;
        //最近公共祖先在cur的左子树
        else if (cur->val > p && cur->val > q)
            cur = cur->left;
        //最近公共祖先在cur的右子树
        else
            cur = cur->right;
    }
}
//最近公共祖先一定是在p、q之间的值