05 August 2008
给n个结点，n可能1个或多个，求这n个结点的最低共同祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
Set<Integer> s = new HashSet<>();
for (TreeNode n : nodes) s.add(n.val);
return lcaHelper(root, s);
}
private TreeNode lcaHelper(TreeNode root, Set<Integer> s) {
if (root == null) return null;
if (s.contains(root.val)) return root;
TreeNode left = lcaHelper(root.left, s);
TreeNode right = lcaHelper(root.right, s);
if (left != null && right != null) return root;
else return (left != null) ? left : right;
}
}
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode lca = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
Set<Integer> targetNodes = new HashSet<>();
for(TreeNode node : nodes) {
targetNodes.add(node.val);
}
dfs(root, targetNodes);
return lca;
}
int dfs(TreeNode root, Set<Integer> nodes) {
if(root == null) return 0;
int leftCount = helper(root.left, nodes);
int rightCount = helper(root.right, nodes);
int foundCount = leftCount + rightCount;
if(nodes.contains(root.val)) {
foundCount++;
}
if(foundCount == nodes.size() && lca == null) {
lca = root;
}
return foundCount;
}
}