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

//----------方法一开始
/*
void getPath(struct TreeNode* tree, int path[], int* k, int target) {
    int i = 0;
    int val = tree->val;
    while (val != target) {
        path[i++] = val;
        if (target < val) tree = tree->left;
        else tree = tree->right;
        val = tree->val;
    }
    path[i++] = val;
    *k = i;
}

int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    int plist[10000], qlist[10000], k1 = 0, k2 = 0, res;
    getPath(root, plist, &k1, p);
    getPath(root, qlist, &k2, q);

    for (int i = 0; i < k1 && i < k2; i++) {
        if (plist[i] == qlist[i]) {
            res = plist[i];
        } else break;
    }
    return res;
}
*/
//---------------方法一结束

//---------------方法二开始
int lowestCommonAncestor(struct TreeNode* root, int p, int q) {
    // write code here
    struct TreeNode* cur = root;
    while (1) {
        if (p < cur->val && q < cur->val)
            cur = cur->left;
        else if (p > cur->val && q > cur->val)
            cur = cur->right;
        else break;
    }
    return cur->val;
}

//---------------方法二结束