Soodye
BAN USERpublic static Node buildTree(List<Relation> data) {
if (data == null || data.isEmpty()) {
return null;
}
Node root = null;
Map<Integer, Node> mapNode = new HashMap<Integer, Node>();
for (Relation relation : data) {
if (relation.parent == null) {
if (mapNode.containsKey(relation.child)) {
root = mapNode.get(relation.child);
} else {
root = new Node(relation.child);
mapNode.put(root.val, root);
}
continue;
}
Node parent;
if (mapNode.containsKey(relation.parent)) {
parent = mapNode.get(relation.parent);
addChild(mapNode, relation, parent);
} else {
parent = new Node(relation.parent);
mapNode.put(parent.val, parent);
addChild(mapNode, relation, parent);
}
}
return root;
}
private static void addChild(Map<Integer, Node> mapNode, Relation relation, Node parent) {
Node childNode = mapNode.containsKey(relation.child) ? mapNode.get(relation.child) : new Node(relation.child);
if (relation.isLeft) {
parent.left = childNode;
} else {
parent.right = childNode;
}
mapNode.put(childNode.val, childNode);
}
public static Collection<Interval> insertAndMergeInterval(Collection<Interval> intervals, Interval toInsert) {
if (toInsert == null) {
throw new IllegalArgumentException();
}
if (intervals == null) {
return Arrays.asList(toInsert);
}
Stack<Interval> result = new Stack<Interval>();
Iterator<Interval> iterator = intervals.iterator();
while (iterator.hasNext()) {
Interval current = iterator.next();
Interval last = result.isEmpty() ? null : result.peek();
if (toInsert != null && toInsert.isBefore(current)) {
if (toInsert.isOverlap(last)) {
last = mergeWithLastInterval(toInsert, result);
} else {
result.push(toInsert);
}
toInsert = null;
}
if (current.isOverlap(last)) {
mergeWithLastInterval(current, result);
} else {
result.push(current);
}
}
if (toInsert != null) {
Interval last = result.isEmpty() ? null : result.peek();
if (toInsert.isOverlap(last)) {
mergeWithLastInterval(toInsert, result);
} else {
result.push(toInsert);
}
}
return result;
}
private static Interval mergeWithLastInterval(Interval current, Stack<Interval> result) {
Interval last = result.pop();
Interval merged = current.merge(last);
return result.push(merged);
}
public static class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public boolean isOverlap(Interval other) {
return (other != null && this.start >= other.start && this.start - 1 <= other.end);
}
public Interval merge(Interval other) {
int start = this.start > other.start ? other.start : this.start;
int end = this.end > other.end ? this.end : other.end;
return new Interval(start, end);
}
public boolean isBefore(Interval other) {
return this.start < other.start;
}
public String toString() {
return "[" + start + ", " + end + "]";
}
}
- Soodye July 26, 2015