202. Segment Tree Query

最后更新

二刷
09-Jan-17

正儿八经线段树的应用了。 查找区间内的值。

对于某一个Node，有这样的可能：
1）需要查找区间和当前NODE没有覆盖部分，那么直接回去就行了。
2）有覆盖的部分，覆盖部分作为新的查找区间，往左右子找。

Time: O(NlgN)
Space: O(lgN) for memory stack

public class Solution {
    public int query(SegmentTreeNode root, int start, int end) {
        if (root == null) return Integer.MIN_VALUE;
        if (end < root.start || start > root.end) return Integer.MIN_VALUE;
        
        int newStart = Math.max(root.start, start);
        int newEnd = Math.min(root.end, end);
        
        if (newStart == root.start && newEnd == root.end) return root.max;
        
        return Math.max(query(root.left, newStart, newEnd), 
                        query(root.right, newStart, newEnd));
    }
}