七. Segment Tree 1 Segment Tree B

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