# [java] 范围交叉算法优于O（n）？

class TreeNode
{
public:
long pivot;
List<Range> leaves;  //Any ranges that intersect the pivot
TreeNode left;        //Tree nodes that fall to the left of the pivot
TreeNode right;       //Tree nodes that fall to the right of the pivot
};

1. 创建范围列表
2. 选择枢轴点（可能使用结束日期的排序列表。）??
3. 建立你的树。

1. 使用二进制搜索来查找> = TestRange.End的第一个数据透视表
2. 遍历树，直到pivot> TestRange.Start

2A。 将叶子添加到结果中。

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

4
--------------+------------------
3             |                 7
|            1-4                |
|            2-4                |
|            0-5                |
|            4-5                |
---------+------                 --------+--------
2        |    null              6        |       null
-----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null
0-2                             2-6
1-2
Question

public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}

- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.