查找范围中包含的bst的最大子树的大小

3 回答

• 1

  假设我们的size函数返回 -1 表示无效子树 . 如果节点的值和其子树中的所有值都在范围内，则（子）树有效 .

  # returns a tuple: (size of T, best valid size among itself and its subtrees)
  def f(x,y,T): 
    if T is None: 
      return (0,0)
  
    l_size, l_best = f(x,y,T.left) 
    r_size, r_best = f(x,y,T.right) 
  
    if x <= T.value <= y and l_size >= 0 and r_size >= 0:
      return (1 + l_size + r_size,1 + l_size + r_size)
    else:
      return (-1,max(l_best,r_best))
  

  回复于 2024-05-10T12:48:17+08:00
• 0

  我们可以递归地解决问题 . 我们需要知道每个子树的左边界和右边界（即最小和最大的元素） . 如果它位于[x，y]范围内，我们可以用当前子树的总大小更新答案 . 下面是一些代码（ solution 函数在答案之上返回一个带有一些额外信息的元组 . 如果只是希望它返回范围内最大子树的大小，你可以将它包装起来并将其用作辅助函数） .

  def min_with_none(a, b):
      """
      Returns the minimum of two elements.   
      If one them is None, the other is returned.
      """
      if a is None:
          return b
      if b is None
          return a
      return min(a, b)
  
  
  def max_with_none(a, b):
      """
      Returns the maximum of two elements.   
      If one them is None, the other is returned.
      """
      if a is None:
          return b
      if b is None:
          return a
      return max(a, b)
  
  
  def solution(x, y, T):
      """
      This function returns a tuple 
      (max size of subtree in [x, y] range, total size of the subtree, min of subtree, max of subtree) 
      """
      if T is None:
          return (0, 0, None, None)
  
      # Solves the problem for the children recursively
      left_ans, left_size, left_min, _ = solution(x, y, T.left)
      right_ans, right_size, _, right_max = solution(x, y, T.right)
  
      # The size of this subtree
      cur_size = 1 + left_size + right_size
  
      # The left border of the subtree is T.val or the smallest element in the
      # left subtree (if it's not empty)
      cur_min = min_with_none(T.val, left_min)
  
      # The right border of the subtree is T.val or the largest element in the 
      # right subtree (if it's not empty)
      cur_max = max_with_none(T.val, right_max)
  
      # The answer is the maximum of answer for the left and for the right 
      # subtree
      cur_ans = max(left_ans, right_ans)
      # If the current subtree is within the [x, y] range, it becomes the new answer,
      # as any subtree of this subtree is smaller than itself
      if x <= cur_min and cur_max <= y:
          cur_ans = cur_size 
  
      return (cur_size, cur_ans, cur_min, cur_max)
  

  该解决方案明确地以线性时间运行，因为它仅访问每个节点一次并且每个节点执行恒定数量的操作 .

  回复于 2024-05-10T12:48:17+08:00
• 0

  对于BST中的每个节点，您可以关联它的有效范围 [Li,Ri] ，这意味着该节点的子树中的所有元素都位于有效范围内 .

  您可以通过递归方式轻松定义这些范围：

  对于节点 i ，假设范围是 [Li, Ri] ，并且此节点中存储的值是 val . 对于 i 的左子，范围是 [Li, val − 1] . 同样对于正确的孩子，范围是 [val + 1, Ri] .

  对于根节点，有效范围是 [−inf, inf] .

  回复于 2024-05-10T12:48:17+08:00