友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.Note:
-
All of the nodes' values will be unique.
-
p and q are different and both values will exist in the binary tree.
思路分析
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;
}