手把手写线段树

题目分析

这道题, 无非就是一段时间可用或者是不可用, 很理所当然的, 我们就可以联想到使用线段树来解决这题

而线段树所具有的属性了就应该是, 这一段时间是否是可用的, 我们可以以此定义一个bool类型的成员

bool available = true;

写一下完整的树的结点:

class TreeNode
{
public:// 树的成员TreeNode* left;TreeNode* right;// 线段树特殊的bool available = true;bool lazy = true;
};

创建线段树

接下来 我们就用上面讲的三步走的方法来书写创建线段树的递归

首先, 对于一颗这样的线段树

来试着创建这棵线段树

1. 首先给这个函数下定义

TreeNode* build(int beg, int end);

定义build函数: 创建一颗线段树, 其的根节点的范围就是[beg, end], 返回这棵线段树的root节点

下完了这个定义, 那我们的build函数就具有了我们下过定义的这个作用!

2. 分析做什么?

以下的三件事:

• 生成根节点, 要把它的范围设置为 [beg ,end]

  TreeNode* root = new TreeNode();root->beg = beg;
  root->end = end;
  

• 构造左子树, 其范围为[beg, mid]

  //创建一颗线段树, 其的根节点的范围就是[beg, mid], 返回这棵线段树的root节点
  root->left = build(beg, mid);
  

• 构造右子树, 其范围为[mid + 1, end]

  root->right = build(mid + 1, end);
  

• 不难看出 我们的mid可以取

  int mid = (beg + end) / 2;
  

3. 什么时候来做

让我们来看看2中分析的三个步骤

不管这三个步骤的顺序是如何, 只要这三个步骤有执行, 手把手这棵线段树就可以生成啊

结果都是一样的

所以 随便!随便!

我们这个函数的大概轮廓就出来了

TreeNode* build(int beg, int end)
{TreeNode* root = new TreeNode();root->beg = beg;root->end = end;// 处理一下边界条件// xxxxxint mid = (beg + end) / 2;root->left = build(beg, mid);root->right = build(mid + 1, end);
}

* 最后, 加小料

• 边界条件

   beg == end;
  

  if(beg == end)
  {return root;
  }
  

• 返回值

  return root;
  

代码示例

@brief 构建一棵线段树 并且返回其root
TreeNode* build(int beg, int end)
{TreeNode* root = new TreeNode();root->beg = beg;root->end = end;if(beg == end){return root;}int mid = (beg + end) / 2;root->left = build(beg, mid);root->right = build(mid + 1, end);return root;
}