LeetCode 题201：线段树的构造

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

题目描述：

线段树是一棵二叉树，它的每个节点包含了两个额外的属性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 方法，接受 start 和 end 作为参数, 然后构造一个代表区间 [start, end] 的线段树，返回这棵线段树的根。
例如：
比如给定start=1, end=6，对应的线段树为：

数据结构：

/**
* class SegmentTreeNode * {* public:*     int start, end;*     SegmentTreeNode *left, *right;*     SegmentTreeNode(): start(0), end(0), left(NULL), right(NULL){} * }**/

代码：

class Solution
{
public:SegmentTreeNode *build(int start, int end) {if(start>end)  return NULL;  SegmentTreeNode *root= new SegmentTreeNode(start,end);  if(start != end){  int mid=start+(end-start)/2;  root->left=build(start,mid);  root->right=build(mid+1,end);  }  return root;  }
};

这篇关于LeetCode 题201：线段树的构造的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---