Idea:
The recursion is required here for every node has two children. (if here is only one child, while loop could be used.)
"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end = start, end
self.left, self.right = None, None
"""
class Solution:
"""
@param: start: start value.
@param: end: end value.
@return: The root of Segment Tree.
"""
def build(self, start, end):
# write your code here
if start > end:
return None
head = SegmentTreeNode(start, end)
if start == end:
return head
def sub_build(node, start, end):
start_1 = start
end_1 = int((start + end)/2)
node_left = SegmentTreeNode(start_1, end_1)
node.left = node_left
if start_1 != end_1:
sub_build(node_left, start_1, end_1)
start_2 = int((start + end)/2 + 1)
end_2 = end
node_right = SegmentTreeNode(start_2, end_2)
node.right = node_right
if start_2 != end_2:
sub_build(node_right, start_2, end_2)
return None
sub_build(head, start, end)
return head
