跳到主要内容

236 - 二叉树的最近公共祖先

题目链接​

题目​

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

思路​

假设当前节点为root，寻找最近公共祖先（LCA）一共会有三种情况：

  1. p和q分别在root的两侧：root是LCA。
  2. p是q的祖先：p是LCA。
  3. q是p的祖先：q是LCA。

解题方法​

使用递归完成，递归查找节点的左右子节点。递归返回条件：当前节点为p或者q。 一共有三种情况：

  1. left !== null && right !== null：左节点的递归返回结果和右节点的递归返回结果都不为空。这说明p和q分别存在与左右子树。说明root是LCA。我们直接返回root作为答案。
  2. left !== null：左节点不为空，右节点为空。这说明左节点是p或者q其中一个，而且另一个是左节点的后代，因为另一个并不存在于右子树，只可能存在于左子树。说明左节点就是我们要找的LCA。
  3. right !== null：右节点不为空，左节点为空。同上。 所以第二种和第三种情况可以简化为：哪边有返回值哪边就是LCA。return left || right。

代码​

/**
 * @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 && right !== null) {
        return root;
    } else {
      return left || right;
    }
};

复杂度​

时间复杂度: O(n)O(n)

空间复杂度: O(n)O(n)