七. Segment Tree 2 Segment Tree Q

Idea:
It is considerable that 4 situations should be included:

1. start, end are all equal to range of node
2. start, end is in the range of node.left
3. start, end is in the range of node.right
4. start is on the range of node.left but end is in the range of node.right.

Therefore, the recursion should be in this way.

"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
    def __init__(self, start, end, max):
        self.start, self.end, self.max = start, end, max
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of segment tree.
    @param start: start value.
    @param end: end value.
    @return: The maximum number in the interval [start, end]
    """
    def query(self, root, start, end):
        # write your code here
       #  start, end are all equal to range of node
        if start == root.start and end == root.end:
            return root.max

        # start, end is in the range of node.left
        if root.left.end < start:
            max = self.query(root.right, start, end)
            return max
        else:
            # start, end is in the range of node.right
            if root.right.start > end:
                max = self.query(root.left, start, end)
                return max
            else:
                # start is on the range of node.left 
                #but end is in the range of node.right.
                max_1 = self.query(root.left, start, root.left.end)
                
                max_2 = self.query(root.right, root.right.start, end)
                
                if max_1 < max_2:
                    return max_2
                else: 
                    return max_1