LeetCode 题247：线段树的查询（2）

2024-08-24 09:08

文章标签 leetcode 查询线段 247

本文主要是介绍LeetCode 题247：线段树的查询（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

对于一个数组，我们可以对其建立一棵线段树, 每个结点存储一个额外的值 count 来代表这个结点所指代的数组区间内的元素个数。(数组中并不一定每个位置上都有元素)

实现一个 query 的方法，该方法接受三个参数 root, start 和end, 分别代表线段树的根节点和需要查询的区间，找到数组中在区间[start, end]内的元素个数。

例如：
对于数组 [0, 空，2, 3], 对应的线段树为：
这里写图片描述
query(root, 1, 1), return 0
query(root, 1, 2), return 1
query(root, 2, 3), return 2
query(root, 0, 2), return 2

数据结构：

/*** Definition of SegmentTreeNode:* class SegmentTreeNode* {* public:*     int start, end, count;*     SegmentTreeNode *left, *right;*     SegmentTreeNode(int start, int end, int count) *     {*         this->start = start;*         this->end = end;*         this->count = count;*         this->left = this->right = NULL;*     }* }

代码：

class Solution 
{
public:int query(SegmentTreeNode *root, int start, int end){if(root == NULL || start > end){return 0;}if(root->start > end || root->end < start){return 0;}if(root->start >= start && root->end <= end){return root->count;}int mid = root->start + (root->end - root->start)/2;  if(start > mid) {return query(root->right,start,end);  }else if(end < mid+1){return query(root->left,start,end);  }else  {return query(root->left,start,mid) + query(root->right,mid+1,end); }}
};