lintcode 202. 线段树的查询
程序员文章站
2022-07-06 10:39:33
...
对于一个有n个数的整数数组,在对应的线段树中, 根节点所代表的区间为0-n-1, 每个节点有一个额外的属性max,值为该节点所代表的数组区间start到end内的最大值。
为SegmentTree设计一个 query 的方法,接受3个参数root, start和end,线段树root所代表的数组中子区间[start, end]内的最大值。
样例
样例 1:
输入:"[0,3,max=4][0,1,max=4][2,3,max=3][0,0,max=1][1,1,max=4][2,2,max=2][3,3,max=3]",1,2
输出:4
解释:
对于数组 [1, 4, 2, 3], 对应的线段树为 :
[0, 3, max=4]
/ \
[0,1,max=4] [2,3,max=3]
/ \ / \
[0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
[1,2]区间最大值为4
样例 2:
输入:"[0,3,max=4][0,1,max=4][2,3,max=3][0,0,max=1][1,1,max=4][2,2,max=2][3,3,max=3]",2,3
输出:3
解释:
对于数组 [1, 4, 2, 3], 对应的线段树为 :
[0, 3, max=4]
/ \
[0,1,max=4] [2,3,max=3]
/ \ / \
[0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
[2,3]区间最大值为3
/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
* int start, end, max;
* SegmentTreeNode *left, *right;
* SegmentTreeNode(int start, int end, int max) {
* this->start = start;
* this->end = end;
* this->max = max;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of segment tree.
* @param start: start value.
* @param end: end value.
* @return: The maximum number in the interval [start, end]
*/
int query(SegmentTreeNode * root, int start, int end) {
// write your code here
int mid=(root->start+root->end)/2;
if(root->start>=start&&root->end<=end) return root->max;
else if(start>mid)return query(root->right,start,end);
else if(end<mid+1)return query(root->left,start,end);
else return max(query(root->left,start,end),query(root->right,start,end));
}
};
上一篇: Tess4J之简单图像识别