一、题目内容 中等

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

百度百科中最近公共祖先的定义为：“对于有根树 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 。 18. 二叉树的最近公共祖先（236） - 图1

示例2：

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

示例3：

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

提示：

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

    二、解题思路

    想找公共祖先，我们平时正常会从下往上找，你想想你肉眼找公共祖先是不是这样做的。
    写程序不可能直接拿到下层节点啊，肯定是要先往下找，然后在往上回溯。
    image.png
    假如现在只有三个节点，先看左子节点，再看右子节点 与 q、p 的关系，然后再看中间节点。
    所以用后序遍历比较好，我们试着来做一下。假设 q = 2，p = 3
  1. 从 1 开始，1 不是 p、q。递归左右子树
  2. 走到 2，是 q。该往上回溯，还是往下递归呢？
    1. 我们肉眼找的时候，找到 p 或 q，就会沿着 p 往上找出所有公共祖先、再找 q 的，看哪个开始重合
    2. 所以应该在这个时候往上回溯了，返回这个节点，说明找到了 q
  3. 后序遍历嘛，所以走到 3，是 p，往上回溯，返回这个节点，说明找到了 p

  4. 回溯到了 1，由于找到了 q 和 p，那么 1 就是公共祖先了，返回节点 1

    1. var lowestCommonAncestor = function (root, p, q) {
    2. // 返回的终止条件是什么呢？
    3. // if() return xxx
    4. const left = lowestCommonAncestor(root.left, p, q)
    5. const right = lowestCommonAncestor(root.right, p, q)
    6. // 在这里操作，判断祖先节点
    7. // if(){}
    8. };

    我们来看看别的例子。
    像下面找到 1 之后，没有子节点，而且不是 p / q 的节点，我们肉眼判断的时候，实际上下一步是什么呢？
    回溯到 10，然后开始遍历 10 的右子树，去找 6 和 5对吧。
    我们假设 1 变成了 6，回溯到 10，10 知道了左子树有 p
    那这个时候就得从 10 的右子树去找 q = 5，如果找到了，那么 10 就是最近公共祖先。
    如果没找到，那么就去找 8 的右子树。是这个逻辑吧
    所以要让 10 知道，它的左右子树，有没有 p 和 q。

  5. 如果 p 在左子树， q 在右子树，反过来也行，那就返回 10 作为节点

  6. 如果 p 在 10 的子树，q 不在，那么回溯到 8

按照这个逻辑，我们可以回溯时

  1. 判断节点的左右子树是否都不为 null，说明节点的左右子树存在 p 和 q，节点就是最近公共祖先节点
    1. 为什么是最近的？因为是从下层往上层遍历，肯定是最近的
  2. 如果只找到一个，p 或 q，那么返回给祖先节点找到的那个，让祖先节点去找它另一个子树
    1. var lowestCommonAncestor = function (root, p, q) {
    2. // 返回的终止条件是什么呢？
    3. // 节点是 p 或 q 就返回，说明找到了
    4. // 节点是 null 也返回，不能往下遍历了
    5. if (root === q || root === p || root === null) return root
    6. const left = lowestCommonAncestor(root.left, p, q)
    7. const right = lowestCommonAncestor(root.right, p, q)
    8. // left 和 right 存在，说明 p 和 q 都找到了，就返回该节点，说明是最近公共祖先
    9. if (left && right) return root
    10. // 想想看，像下面的 7 就是最近公共祖先，返回之后，是 10 的右子树存在
    11. // 而 10 的左子树不存在，是 null
    12. // 我们要往上推送节点 7，所以把存在的那个节点，返回给上层
    13. if (left && !right) return left
    14. else if (!left && right) return right
    15. else return null
    16. };
    image.png

三、具体代码

  1. /**
  2.  * @param {TreeNode} root
  3.  * @param {TreeNode} p
  4.  * @param {TreeNode} q
  5.  * @return {TreeNode}
  6.  */
  7. var lowestCommonAncestor = function (root, p, q) {
  8.   if (root === p || root === q || root === null) return root
  9.   const left = lowestCommonAncestor(root.left, p, q)
  10.   const right = lowestCommonAncestor(root.right, p, q)
  11.   if (left && right) return root
  12.   if (!left && right) return right
  13.   else if (left && !right) return left
  14.   else return null
  15. };

四、其他解法