MIS硕士，一个口音纯正的美国人面的。
给一个binary tree， 要求return the maximum length of unconnected sets。leetcode上也没刷过，卡了一下（很久）做出来了。unconnected set就是说一个set里面所有node都不相邻。
class Node {
Node left;
Node right;
}
public int longestUnConnected(Node root) {
Map<Integer, Set<Node>> levelMap = levelTaversal(root);
Map<Integer, Integer> levelSize = new HashMap<>();
for (Map.Entry<Integer, Set<Node>> mapEntry : levelMap.entrySet()) {
levelSize.put(mapEntry.getKey(), mapEntry.getValue().size());
}
int[] dp = new int[levelMap.size() + 1];
dp[0] = 0;
dp[1] = levelSize.get(1);
int max = Integer.MIN_VALUE;
int res = Integer.MIN_VALUE;
for (int i = 2; i < dp.length; i++) {
for (int j = 0; j < i - 1; j++) {
max = Math.max(max, dp[j]);
}
dp[i] = max + levelSize.get(i);
max = Integer.MIN_VALUE;
}
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
public Map<Integer, Set<Node>> levelTaversal(Node root) {
Map<Integer, Set<Node>> res = new HashMap<>();
Queue<Node> q = new LinkedList<>();
q.add(root);
int index = 1;
while (!q.isEmpty()) {
int qLen = q.size();
Set<Node> s = new HashSet<>();
for (int i = 0; i < qLen; i++) {
Node node = q.poll();
s.add(node);
if (node.left != null)
q.offer(node.left);
if (node.right != null)
q.offer(node.right);
}
res.put(index, s);
index++;
}
return res;
}