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

/**
 * 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 ) {
    // write code here
    int big, small, ans;
    p > q ? (big = p, small = q ) : (big = q, small = p);
    while (root) {
        if (root->val >= small && root->val <= big) {
            return  root->val;
        } else if (root->val < small) {
            return lowestCommonAncestor(root->right, big, small);
        } else if (root->val > big) {
            return lowestCommonAncestor(root->left, big, small);
        }
    }
    return 0;
}

因为BST中节点的值不重复

法一：记录p,q的查找路径再比较 因此最坏情况二叉搜索树形状类似单链表 时空复杂度：O(n)

step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左 子树，直到找到目标节点。这个过程成用数组记录遇到的元素。

step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。

step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先

法二：递归查找 因此最坏情况二叉搜索树形状类似单链表，则要递归至最底层 时空复杂度：O(n)，

step 1：首先检查空节点，空树没有公共祖先。

step 2：对于某个节点，比较与p、q的大小，若p、q在该节点两边说明这就是最近公共祖先。这里最关键，想不到也没辙

step 3：如果p、q都在该节点的左边，则递归进入左子树。

step 4：如果p、q都在该节点的右边，则递归进入右子树。