题目
输入两个树结点，求它们的最低公共祖先。这棵树是普通的树，而且树中的结点没有指向父结点的指针。
实现
1
2
3
4
5
6
7
8
|
public class {
int val = 0;
List<TreeNode> children = new ArrayList<>();
public (int val) {
this.val = val;
}
}
|
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
|
public TreeNode getLastCommonParent(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null || node1 == null || node2 == null)
return null;
List<TreeNode> path1 = new ArrayList<>();
getPath(path1, root, node1);
List<TreeNode> path2 = new ArrayList<>();
getPath(path2, root, node2);
Iterator<TreeNode> iterator1 = path1.iterator();
Iterator<TreeNode> iterator2 = path2.iterator();
TreeNode parent = null;
while (iterator1.hasNext() && iterator2.hasNext()) {
TreeNode n1 = iterator1.next();
TreeNode n2 = iterator2.next();
if(n1 != n2)
break;
parent = n1;
}
return parent;
}
private void getPath(List<TreeNode> path, TreeNode root, TreeNode node) {
if (root == null)
return;
path.add(root);
if (root == node)
return;
for (TreeNode child : root.children) {
getPath(path, child, node);
if (path.contains(node))
break;
}
if (!path.contains(node))
path.remove(path.size() - 1);
}
|
近期评论