友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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, 105]内。 -
-109 <= Node.val <= 109 -
所有
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;
}
}