【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;
};

# 更多资料

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