本文主要是介绍LeetCode 题439：线段树的构造（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
线段树是一棵二叉树，它的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:
–>根节点的 start 和 end 由 build 方法所给出。
–>对于节点 A 的左儿子，有start=A.left, end=(A.left + A.right) / 2。
–>对于节点 A 的右儿子，有start=(A.left + A.right) / 2 + 1, end=A.right。
–>如果 start 等于 end, 那么该节点是叶子节点，不再有左右儿子。
对于给定数组设计一个build方法，构造出线段树
例如：
给出[3,2,1,4]，线段树将被这样构造
分析：
这道题与之前线段树构造的区别在于：每个结点除了需要知道所管辖的区间范围[start, end]以外，还需要存储一个当前区间内的最大值max。通过观察我们得到：叶子结点的max域为数组对应下标的元素值，非叶子结点的max域则通过自底向上的计算由两个儿子结点的max域比较得出。
数据结构：
/*** 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;* }* //SegmentTreeNode(): start(0), end(0), max(0), left(NULL), right(NULL){} * }**/
代码：
class Solution
{
public:SegmentTreeNode *build(vector<int> &arr) {return buildTree(0, arr.size()-1, arr );}SegmentTreeNode *buildTree(int start, int end, vector<int> &arr){if(start>end) return NULL; SegmentTreeNode *root= new SegmentTreeNode(start, end, arr[start]);if(start != end){ int mid=start+(end-start)/2; root->left=buildTree(start, mid, arr); root->right=buildTree(mid+1, end, arr); if(root->left != NULL && root->left->max > root->max){root->max = root->left->max;}if(root->right != NULL && root->right->max > root->max){root->max = root->right->max;}} return root;}
};
这篇关于LeetCode 题439：线段树的构造（2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
