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

/**
 * 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 ) {
  //如果p、q分散在节点两边，这个节点一定是公共祖先。
  //如果p、q同时在左边或同时在右边，这个节点一定！！不是！！公共祖先。
  //p、q为父子节点，则父亲为公共祖先，由于是自上而下搜索，第一个搜索到的一定是父节点。
  //综上，只要p、q不是在同侧即为祖先节点
    struct TreeNode* tmp=root;
    while(1){
        if(p<tmp->val&&q<tmp->val){
            tmp=tmp->left;
        }else if (p>tmp->val&&q>tmp->val) {
            tmp=tmp->right;
        }else{
            return tmp->val;
        }
    }
}