重启DAY8 二叉树的最近公共祖先

跟着灵茶山艾府大佬学习算法思路的day8，目标是在一个月内掌握hot100

b站链接如下：

二叉树的最近公共祖先【基础算法精讲 12】

二叉树的最近公共祖先 题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

思路：

这里一共主要涉及这么几个变量：在递归中的当前节点、需要找到的最近公共祖先节点、q节点和p节点。当前节点是动态的，而其他几个节点是静态的，公共祖先是未知的，其他的都是已知的。那么根据当前节点和pq节点的几种关系，可以分为下面四种情况。

在递归过程中到达了p节点或者q节点，pq要么就是要找的祖先，要么祖先在pq的上方，无论如何pq的下方都不需要再寻找了。如果pq分布在本节点的左右子树，那么本节点就是最近公共祖先，可以直接返回。如果只有左子树或者右子树找到，那么最近公共祖先一定在那棵子树中。

讨论完的结果就会是如下：

问：lowestCommonAncestor 函数的返回值是什么意思？

答：返回值的准确含义是「最近公共祖先的候选项」。对于最外层的递归调用者来说，返回值是最近公共祖先的意思。但是，在递归过程中，返回值可能是最近公共祖先，也可能是空节点（表示子树内没找到任何有用信息）、节点 p 或者节点 q（可能成为最近公共祖先，或者用来辅助判断上面的某个节点是否为最近公共祖先）。

问：为什么发现当前节点是 p 或者 q 就不再往下递归了？万一下面有 q 或者 p 呢？

答：如果下面有 q 或者 p，那么当前节点就是最近公共祖先，直接返回当前节点。如果下面没有，那既然都没有要找的节点了，也不需要递归，直接返回当前节点。

代码：

var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) {
        return root; // 找到 p 或 q 就不往下递归了，原因见上面答疑
    }
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) { // 左右都找到
        return root; // 当前节点是最近公共祖先
    }
    // 如果只有左子树找到，就返回左子树的返回值
    // 如果只有右子树找到，就返回右子树的返回值
    // 如果左右子树都没有找到，就返回 null（注意此时 right = null）
    return left ?? right;
};

总结：

感觉自己想不到这题要用递归做，递归的过程好像也没那么好理解。

二叉搜索树的最近公共祖先 题目描述：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：

可以利用二叉搜索树的性质，例如说p和q的节点值都小于当前节点值，那么p和q就在当前节点的左子树中，那么最近公共祖先也在左子树，递归左子树就好。反过来也是一样的，p和q都大于当前节点值，p和q就在右子树中。如果p和q分别在左右子树，也就是当前节点的值从上到下递归时，第一次处于p与q的值之间（第一次进入p和q的值区间内，如果在最近祖先节点上方，当前节点值是严格大于或小于子树的值的），那么最近公共祖先也就是当前节点。

当节点遍历到p或者q时，因为已经讨论了上方的情况（包含了p和q在左右子，或者p和q分别在左右子的其他情况），所以此时p或者q就一定只能是最近公共祖先了。

相较于上一题，这道题是不会递归到空节点的，所以不需要判断空节点。用3个节点的例子模拟一下便知。

所以可以分为以下几种情况：

代码：

var lowestCommonAncestor = function(root, p, q) {
    const x = root.val;
    if (p.val < x && q.val < x) { // p 和 q 都在左子树
        return lowestCommonAncestor(root.left, p, q);
    }
    if (p.val > x && q.val > x) { // p 和 q 都在右子树
        return lowestCommonAncestor(root.right, p, q);
    }
    return root; // 其它情况返回当前节点
    // 总的来说，一旦有某个值被return，由于递归调用放在return中，那个值会被一直传递到最上层递归
};

总结：

思路貌似比上一道题要简单一点，因为可以利用二叉搜索树的性质来提前得知pq与当前节点的位置关系。