线段树的构造
描述
线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:
- 根节点的 start 和 end 由 build 方法所给出。
- 对于节点 A 的左儿子,有 start=A.left, end=(A.left + A.right) / 2。
- 对于节点 A 的右儿子,有 start=(A.left + A.right) / 2 + 1, end=A.right。
- 如果 start 等于 end, 那么该节点是叶子节点,不再有左右儿子。
- 实现一个 build 方法,接受 start 和 end 作为参数, 然后构造一个代表区间 [start, end] 的线段树,返回这棵线段树的根。
样例
比如给定start=1, end=6,对应的线段树为:
[1, 6]
/ \
[1, 3] [4, 6]
/ \ / \
[1, 2] [3,3] [4, 5] [6,6]
/ \ / \
[1,1] [2,2] [4,4] [5,5]
考察点
- 递归算法
答案
public SegmentTreeNode build(int start, int end) {
if (start > end) {
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end);
// write your code here
if (start == end) {
return root;
} else {
root.left = new SegmentTreeNode(root.start, (root.start + root.end) / 2);
root.right = new SegmentTreeNode((root.start + root.end) / 2 + 1, root.end);
buildChild(root.left);
buildChild(root.right);
}
return root;
}
public void buildChild(SegmentTreeNode node) {
if (node.start != node.end) {
node.left = new SegmentTreeNode(node.start, (node.start + node.end) / 2);
node.right = new SegmentTreeNode((node.start + node.end) / 2 + 1, node.end);
buildChild(node.left);
buildChild(node.right);
}
}