236. Lowest Common Ancestor of a Binary Tree

题干简述：

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

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

解题思路

之前，有做过一道类似的题目：235. Lowest Common Ancestor of a Binary Search Tree。本题和 No.235 的最大，也是本质上的区别，在于本题所操作的二叉树是一个普通的二叉树，而 No.235 中操作的是 BST 二叉检索树。得益于二叉检索树的有序性，No.235 很好解决。但是，一个普通的二叉树，我们如何找到指定两个节点的最近公共祖先呢？

首先，让我们仔细看下 LCA 最近公共祖先的定义：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）”。假设我们已经找到了这个 LCA 结点 X，那么，X必然满足以下几种情况之一：

  • X 为 p 或 q 其中某一个，另一个结点在 X 的子树中：

    image

  • X 不为 p 或 q 其中某一个，p，q 分别在 X 的左右子树中：

    image

这样，我们就可以确定 X 满足的条件。提到条件，是不是脑海里立刻回想起递归了？没错，这个条件，就是我们递归的决定返回值的条件。让我们梳理一下递归的四步：

  • 输入参数：传入 root 结点；
  • 函数的功能/目的：获取当前树中（假定）存在的 p，q 的 LCA 结点；
  • 终止条件：输入结点为叶子结点时，又或输入结点等于 p 或 q 时；
  • 返回值：这里的返回值需要我们好好思考一下，返回值肯定是当前树中，p，q 的 LCA 结点，问题是我们如何拿到它。结合上面梳理出的 LCA 结点 X 的条件，假定树根节点为 r，递归 r 的左子树得到结果为 left，递归 r 的右子树得到结果为 right，我们不难得出如下条件判断：
    1. r 为 null 或者 r === p 或 r === q 时，X 的值为 r 自身，返回 r；
    2. r 不为 null，left 为 null，此时说明 r 的左子树中不包含 p，q，因此最终结果必然为 right；
    3. r 不为 null，right 为 null，此时说明 r 的右子树中不包含 p，q，因此最终结果必然为 left；
    4. r，left，right均 不为 null，此时说明 p，q 分别位列 r 左右子树，此时最终结果应为 r；

通过上面的递归四步的梳理，我们就可以写出最终的答案了。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left === null) return right;
    if (right === null) return left;
    return root;
};

Q.E.D.

Take it easy