LeetCode: 236. 二叉树的最近公共祖先

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

236. 二叉树的最近公共祖先

LeetCode - 236. 二叉树的最近公共祖先

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 10⁵] 内。
-10⁹ <= Node.val <= 10⁹
所有 Node.val 互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

思路分析

D瓜哥的思路：先找出一条从根节点到某个节点的路径；然后从这条路径上以此去寻找另外一个节点。找到这返回此节点。

思考题：如何按照"路径"的思路实现一遍？

这道题是 235. Lowest Common Ancestor of a Binary Search Tree 的延伸。但是，解题思路略有不同，本体的解题思路也可用于前者。

有两种情况：

两个节点是一个树下的两个节点；
一个节点就是另外一个节点的祖先节点；

根据这两点，针对一棵树进行递归遍历，去寻找当前节点与两个指定节点相等的节点，找到就返回当前节点（也就是两个节点其中之一），找不到就返回 null。

当左右子树都返回不为 null 时，那么当前节点就是两棵树的公共祖先节点。情况如下：

 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
private TreeNode result;

/**
 * Runtime: 9 ms, faster than 23.17% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
 *
 * Memory Usage: 45.5 MB, less than 5.55% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
 *
 * Copy from: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/[Lowest Common Ancestor of a Binary Tree solution - LeetCode]
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    recurseTree(root, p, q);
    return this.result;
}

private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
    if (Objects.isNull(currentNode)) {
        return false;
    }

    int left = recurseTree(currentNode.left, p, q) ? 1 : 0;

    int right = recurseTree(currentNode.right, p, q) ? 1 : 0;

    int mid = (currentNode.equals(p) || currentNode.equals(q)) ? 1 : 0;

    if (left + mid + right >= 2) {
        this.result = currentNode;
    }
    return (left + mid + right) > 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * 参考 左程云《程序员代码面试指南》的解法
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-24 21:08:59
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) {
    return root;
  }
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  if (left != null && right != null) {
    return root;
  }
  return left != null ? left : right;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-14 21:42:37
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root.val == p.val || root.val == q.val) {
    return root;
  }
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  return left == null ? (right == null ? null : right) : left;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-10 21:09:37
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null) {
    return null;
  }
  if (root.val == p.val || root.val == q.val) {
    return root;
  }
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  if (left != null && right != null) {
    return root;
  } else {
    return left != null ? left : right;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-10-23 20:52:53
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (Objects.isNull(root) || root == p || root == q) {
    return root;
  }
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  // 左右子树返回值都不为空，则 p 和 q 分别在左右子树上
  if (left != null && right != null) {
    return root;
  }
  // 如果只有左子树找到，就返回左子树的返回值
  // 如果只有右子树找到，就返回右子树的返回值
  // 如果左右子树都没有找到，就返回 null（注意此时 right = null）
  return left != null ? left : right;
}

 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-13 20:28
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  return dfs(root, p, q);
}

private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null) {
    return null;
  }
  if (root == p || root == q) {
    return root;
  }
  TreeNode left = dfs(root.left, p, q);
  TreeNode right = dfs(root.right, p, q);
  if (left == null) {
    return right;
  }
  if (right == null) {
    return left;
  }
  if (left != right) {
    return root;
  }
  return null;
}

LeetCode: 236. 二叉树的最近公共祖先

友情支持

236. 二叉树的最近公共祖先

思路分析

参考资料