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

# 解法 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 解法 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 更多资料

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

来自: 【LeetCode 236.二叉树的最近公共祖先】双解法:递归实现 + 利用父指针 | 心谭博客
作者:心谭
Star仓库:github