美文网首页数据结构
201. 线段树的构造

201. 线段树的构造

作者: 6默默Welsh | 来源:发表于2018-01-28 16:47 被阅读12次

描述

线段树是一棵二叉树,他的每个节点包含了两个额外的属性startend用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

  • 根节点的 startendbuild 方法所给出。
  • 对于节点 A 的左儿子,有 start=A.left, end=(A.left + A.right) / 2
  • 对于节点 A 的右儿子,有 start=(A.left + A.right) / 2 + 1, end=A.right
  • 如果 start 等于 end, 那么该节点是叶子节点,不再有左右儿子。

实现一个 build 方法,接受 startend 作为参数, 然后构造一个代表区间 [start, end]的线段树,返回这棵线段树的根。

说明

线段树(又称区间树), 是一种高级数据结构,他可以支持这样的一些操作:

  • 查找给定的点包含在了哪些区间内
  • 查找给定的区间包含了哪些点
    见百科:
    线段树
    区间树

样例

比如给定start=1, end=6,对应的线段树为:

               [1,  6]
             /        \
      [1,  3]           [4,  6]
      /     \           /     \
   [1, 2]  [3,3]     [4, 5]   [6,6]
   /    \           /     \
[1,1]   [2,2]     [4,4]   [5,5]

代码

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param start: start value.
     * @param end: end value.
     * @return: The root of Segment Tree.
     */
    public SegmentTreeNode build(int start, int end) {
        return buildHelper(start, end);
    }
    
    private SegmentTreeNode buildHelper(int start, int end) {
        // 区间异常
        if (start > end) {
            return null;
        }
        
        // 遇到叶子结点
        if (start == end) {
            return new SegmentTreeNode(start, end);
        }
        
        // 分治 + 递归
        int mid = start + (end - start) / 2;
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        root.left = buildHelper(start, mid);
        root.right = buildHelper(mid + 1, end);
        
        return root;
    }
}

相关文章

  • 201. 线段树的构造

    描述 线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start...

  • LintCode 线段树系列问题(线段树的构造,线段树的构造||

    线段树(又称区间树), 是一种高级数据结构,他可以支持这样的一些操作: 查找给定的点包含在了哪些区间内 查找给定的...

  • Java 算法-线段树的修改

      首先说明一下,看这个博客之前,最好有线段树的基本概念,比如说线段树的构造、线段树的查询之类的。最近在学习ANd...

  • 线段树

    线段树 主要是涉及到线段树的思路。构造和一些简单的应用。线段树的应用比较集中,主要是用来处理数组结构里的一些快速查...

  • lintcode-线段树的构造

  • Java 算法 - 进程序列

    题意 样例 1.解题思路   说实话,才开始我的思路是:使用线段树来构造,因为这个题符合的线段树的特性,但是写的时...

  • 439. 线段树的构造 II

    描述 线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start...

  • 数据结构-线段树

    实现一个线段树 下面实现的线段树,有三个功能: 把数组构建成一颗线段树 线段树的修改 线段树的查询 303号问题 ...

  • 算法模板(七) 线段树

    线段树单点操作 线段树区间操作

  • 线段树系列之——区间更新

    第三篇线段树了——重点不在于解决题目,通过题目理解线段树才是重点 前面写了一篇关于线段树的单点更新,线段树的单点更...

网友评论

    本文标题:201. 线段树的构造

    本文链接:https://www.haomeiwen.com/subject/mphzaxtx.html