【LeetCode 236.二叉树的最近公共祖先】双解法：递归实现 + 利用父指针

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

# 解法 1: 递归实现（推荐）

这题相较于 LeetCode 235.二叉搜索树的最近公共祖先 的递归思考起来比较有难度。

封装一个 recurseTree 递归函数，它返回 true/false，代表当前二叉树中是否存在 p、或者存在 q、或者两个节点都存在。在 recurseTree 递归过程中，如果发现当前二叉树同时存在 p 和 q，那么就更新最近公共祖先。

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 原文地址：https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-binary-tree/
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  let res = root;
  recurseTree(root);
  return res;

  /**
   * @return {Boolean} 以node为根的二叉树中是否有p或者q
   */
  function recurseTree(node) {
    if (!node) return false;

    const left = recurseTree(node.left, p, q) ? 1 : 0;
    const right = recurseTree(node.right, p, q) ? 1 : 0;
    const mid = p === node || q === node ? 1 : 0;

    // 如果p和q都出现在以node为根的二叉树中
    if (left + right + mid >= 2) {
      res = node;
    }

    return left + right + mid > 0;
  }
};

# 解法 2: 利用父指针

父指针的关系可以保存在一个哈希表中：<node, node'parent>。那么对 node 来说，它的所有祖先节点就是从 node 开始，一直向上遍历父亲节点，统计过程中所有经历的节点，这些节点组成的集合就是所有祖先节点。

整体思路如下：

1. 遍历二叉树，直到 p 和 q 都被遍历完
2. 统计 p 的所有祖先节点，放入集合 set 中
3. 从 q 开始，不断向上访问祖先节点，每次都检查节点是否在集合 set 中

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 原文地址：https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-binary-tree/
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  const queue = [root];
  const map = new Map();
  map.set(root, null);

  while (!map.has(p) || !map.has(q)) {
    const first = queue.shift();
    if (first.left) {
      map.set(first.left, first);
      queue.push(first.left);
    }
    if (first.right) {
      map.set(first.right, first);
      queue.push(first.right);
    }
  }

  const ancestors = new Set();
  while (p) {
    ancestors.add(p);
    p = map.get(p);
  }

  while (!ancestors.has(q)) {
    q = map.get(q);
  }

  return q;
};

# 更多资料

整理不易，若对您有帮助，请给个「关注+点赞」，您的支持是我更新的动力 👇

• 📖Blog：剑指 Offer 题解 + JS 代码
• 🐱Github ：https://github.com/dongyuanxin/blog
• 🌟 公众号：心谭博客