LintCode 201 [Segment Tree Build]

原題

セグメントツリーは、ノードが表す区間を表す2つの追加のプロパティstartとendを含む2つのツリーです.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に等しい場合、このノードは葉ノードであり、左右の息子はいない.パラメータとしてstartとendを受け入れ、区間[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:
class SegmentTreeNode:
    def __init__(self, start, end):
        self.start, self.end = start, end
        self.left, self.right = None, None
"""

class Solution: 
    # @param start, end: Denote an segment / interval
    # @return: The root of Segment Tree
    def build(self, start, end):
        if start > end:
            return None
            
        root = SegmentTreeNode(start, end)
        if start != end:
            mid = (start + end) / 2
            root.left = self.build(start, mid)
            root.right = self.build(mid + 1, end)
        
        return root