题目链接：https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Given a data stream input of non-negative integers a1, a2,
..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

思路：

建立一棵二叉搜索树，树的节点值用interval表示，其实就是类似于“区间树”节点值是个区间，这些区间不相交。建立树之后中序遍历输出结果。

插入的过程较为麻烦，插入需要考虑一个节点的两端点，情况较多，具体见代码注释。

算法：

public class SummaryRanges {
Node root;

/** Initialize your data structure here. */
public SummaryRanges() {

}

public void addNum(int val) {
if (root == null) {
Interval v = new Interval(val, val);
root = new Node(v, null, null);
} else {
searchAndAdjust(root, val);
}
}

/**
* 搜索并调整树
*/
public void searchAndAdjust(Node node, int val) {
// 若插入val在树左边，插入并调整
if (node.val.start == val + 1) { // 若满足合并条件
node.val.start = val;// 修改区间
if (node.left != null) {// 调整左边
if (node.left.right == null) {// 若左孩子的右孩子为空
if (node.left.val.end + 1 == val) {// 若左孩子可以和父结点合并
node.val.start = node.left.val.start;
node.left = node.left.left;
}
} else {// 若左孩子的右孩子不为空
Node tmp = node.left;
Node parent = tmp;
while (tmp.right != null) {// 一直走到node节点左孩子的最右节点
parent = tmp;
tmp = tmp.right;
}
if (tmp.val.end + 1 == val) {// 若可以和根节点合并
node.val.start = tmp.val.start;
parent.right = tmp.left;
}
}
}
return;
}
if (node.val.start > val + 1) {
if (node.left == null) {// 无法合并区间时 新建节点
Interval v = new Interval(val, val);
Node newNode = new Node(v, null, null);
node.left = newNode;
return;
} else {// 进入下一层搜索
searchAndAdjust(node.left, val);
}
}
// ======end
// 若插入val在树右边，插入并调整，同上
if (node.val.end == val - 1) {
node.val.end = val;
if (node.right != null) {
if (node.right.left == null) {
if (node.right.val.start - 1 == val) {
node.val.end = node.right.val.end;
node.right = node.right.right;
}
} else {
Node tmp = node.right;
Node parent = tmp;
while (tmp.left != null) {// 一直走到node节点左孩子的最右节点
parent = tmp;
tmp = tmp.left;
}
if (tmp.val.start - 1 == val) {// 若可以和根节点合并
node.val.end = tmp.val.end;
parent.left = tmp.right;
}
}
}
return;
}
if (node.val.end < val - 1) {
if (node.right == null) {
Interval v = new Interval(val, val);
Node newNode = new Node(v, null, null);
node.right = newNode;
return;
} else {
searchAndAdjust(node.right, val);
}
}

}

public List<Interval> getIntervals() {
List<Interval> res = new ArrayList<Interval>();
res = inorder(root, res);
return res;
}

public List<Interval> inorder(Node node, List<Interval> res) {
if (node != null) {
res = inorder(node.left, res);
res.add(node.val);
res = inorder(node.right, res);
}
return res;
}

class Node {
Interval val;
Node left, right;

public Node(Interval val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}