python - 构建线段树时是否需要检查是否 lo > hi

Question

下面的代码是流行线段树代码的略微修改版本。

我的问题是为什么我们需要在递归构建树时进行 lo > hi 检查，我想不出一个 lo 永远大于 hi 的例子，因为在任何时候它们都等于 [2,2]递归不会更深入。

class SegmentNode:

  def __init__(self, start, end):

    self.value = 0
    self.start = start
    self.end = end
    self.left = None
    self.right = None

class SegmentTree:

  def __init__(self, nums):

    self.root = self.buildTree(nums, 0, len(nums)-1)


  def buildTree(self, nums, lo, hi):

    if lo > hi:
      return None

    if lo == hi:
      curr = SegmentNode(lo, hi)
      curr.value = nums[lo]
      return curr

    mid = (lo + hi)//2

    curr = SegmentNode(lo, hi)
    curr.left = buildTree(lo, mid)
    curr.right = buildTree(mid+1, hi)

    curr.value = curr.left.value + curr.right.value

    return curr

Answer 1

I cannot think of an example where lo will ever be greater than hi

  def __init__(self, nums):

    self.root = self.buildTree(nums, 0, len(nums)-1)


  def buildTree(self, nums, lo, hi):

    if lo > hi:
      return None

一个例子是:

如果将一个空列表作为 nums 传递给 __init__，则调用 buildTree 并使用 0 作为 lo和 -1 作为 hi。