Idea:
It is considerable that 4 situations should be included:
- start, end are all equal to range of node
- start, end is in the range of node.left
- start, end is in the range of node.right
- 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
