题目描述
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
例子：对于下面这棵二叉树
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
思路
注意：这里是二叉树，并非二叉查找树！
在二叉树中递归查找这两个元素的过程中，将这两个元素路径上的父节点都加入到两个list中
从头访问list元素较少的那个list，判断其元素是否存在于另一个list中，存在即找到公共祖先，不存在则没有公共祖先
如何将元素所有的祖先都加入到list且是按照由近祖先到远祖先的顺序？
1、从二叉树的根节点开始，判断当前节点是否为tar，是则添加到list里，返回true
2、当前节点 != tar，递归左子树，并判断递归函数返回的结果：
i、如果为true，表示找到tar了，将当前结点加入到list，返回true，因为当前节点就是祖先！
ii、如果为false，表示没找到tar，则递归右子树，并判断递归函数返回的结果，判断的处理逻辑同上！
代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
| public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
// exp
if(A.val == root.val || B.val == root.val) {
return root;
}
// init stack to hold father
ArrayList<TreeNode> listA = new ArrayList<>();
ArrayList<TreeNode> listB = new ArrayList<>();
// find A
findLoc(root, A, listA);
findLoc(root, B, listB);
// find common root
if(listA.size() < listB.size()) {
for(int i = 0; i < listA.size(); i++) {
if(listB.contains(listA.get(i))) {
return listA.get(i);
}
}
return null;
}else {
for(int i = 0; i < listB.size(); i++) {
if(listA.contains(listB.get(i))) {
return listB.get(i);
}
}
return null;
}
}
// 当前节点找不到，找左子树，左子树找不到，找右子树
private boolean findLoc(TreeNode root, TreeNode tar, ArrayList<TreeNode> list) {
if(root == null) {
return false;
}
if(root.val == tar.val) {
list.add(root);
return true;
}
if(!findLoc(root.left, tar, list)) { // 当前节点未找到，且左子树没找到
if(findLoc(root.right, tar, list)) { // 右子树找到了
list.add(root);
return true;
}else { // 右子树没找到
return false;
}
}else { // 当前节点没找到，左子树找到了
list.add(root);
return true;
}
}
|
考察点