LC 236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路一：
- dfs，向左节点找 p 和 q，向右节点找 p 和 q，只要能找到一个节点，就返回
- 判断左右节点是否都有返回值
- 若有，则说明左右节点分别有 p 和 q，则此节点为公共祖先节点
- 若没有，则说明两个节点在同一个左节点或右节点中，则只要返回有返回的那个点就行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null) {
return root;
}
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
if (l != null && r != null) {
return root;
} else if (l == null) {
return r;
} else {
return l;
}
}
}
|
思路二：
- 使用 hashmap 记录每个节点的父节点，同时记录 p 和 q 的高度
- 将高度较高的 p 或 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
38
39
40
|
class Solution {
HashMap<TreeNode, TreeNode> map = new HashMap<>();
int lvP = 0, lvQ = 0;
TreeNode p, q;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.p = p;
this.q = q;
dfs(root, 0);
while (lvP > lvQ) {
p = map.get(p);
lvP--;
}
while (lvQ > lvP) {
q = map.get(q);
lvQ--;
}
while (p != q) {
p = map.get(p);
q = map.get(q);
}
return p;
}
void dfs(TreeNode node, int level) {
if (node == p) {
lvP = level;
}
if (node == q) {
lvQ = level;
}
if (node.left != null) {
map.put(node.left, node);
dfs(node.left, level + 1);
}
if (node.right != null) {
map.put(node.right, node);
dfs(node.right, level + 1);
}
}
}
|