友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1650. Lowest Common Ancestor of a Binary Tree III
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for Node is below:
1
2
3
4
5
6
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
According to the definition of LCA on Wikipedia: The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).
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.Example 3:
**Input:** root = [1,2], p = 1, q = 2
**Output:** 1Constraints:
-
The number of nodes in the tree is in the range
[2, 105]. -
-109 ⇐ Node.val ⇐ 109 -
All
Node.valare unique. -
p != q -
pandqexist in the tree.
思路分析
这道题披着树的外衣，里面确实一个链接相交的芯。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-26 20:00:58
*/
public Node lowestCommonAncestor(Node p, Node q) {
if (Objects.isNull(p) || Objects.isNull(q)) {
return null;
}
Node a = p;
Node b = q;
while (a != b) {
if (a == null) {
a = q;
} else {
a = a.parent;
}
if (b == null) {
b = p;
} else {
b = b.parent;
}
}
return a;
}