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

解法 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
• 🌟 公众号：心谭博客