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

心谭博客

发布于 2020-04-21 12:01:28

2850

发布于 2020-04-21 12:01:28

文章被收录于专栏：YuanXin

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

解法 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 开始，一直向上遍历父亲节点，统计过程中所有经历的节点，这些节点组成的集合就是所有祖先节点。

整体思路如下：

遍历二叉树，直到 p 和 q 都被遍历完
统计 p 的所有祖先节点，放入集合 set 中
从 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;
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法