在 Python 中,在 O(n) 时间和 O(1) 空间内查找 BST 的中位数

pythonserver side programmingprogramming更新于 2025/10/10 18:52:17

假设我们有二叉搜索树 (BST),我们必须找到它的中位数。我们知道,对于偶数个节点,中位数 = ((n/2th 节点 + (n+1)/2th 节点) /2 对于奇数个节点,中位数 = (n+1)/2th 节点。

因此,如果输入如下

则输出为 7

要解决此问题,我们将遵循以下步骤 −

  • 如果 root 与 None 相同,则

    • 返回 0

  • node_count := 中的节点数树

  • count_curr := 0

  • current := root

  • 当 current 不为空时,执行

    • 如果 current.left 为空,则

      • count_curr := count_curr + 1

      • 如果 node_count mod 2 不为 0 且 count_curr 与 (node_count + 1) /2 相同,则

        • 返回 previous.data

      • 否则,当 node_count mod 2 为 0 且 count_curr 与 (node_count/2) +1 相同时,则

        • 返回 (previous.data + current.data) /2

      • previous := current

      • current := current.right

    • 否则,

      • previous := current.left

      • 当 previous.right 不为空且 previous.right 与 current 不同时,执行

        • previous := previous.right

      • 如果 previous.right 为空,则

        • previous.right := current

        • current := current.left

      • 否则,

        • previous.right := None

        • previous := previous

        • count_curr := count_curr + 1

        • 如果 node_count mod 2 不为 0 且 count_curr 与 (node_count + 1) / 2 相同,则

          • 返回 current.data

        • 否则,当 node_count mod 2 为 0 且 count_curr 与 (node_count / 2) + 1 相同时,则

          • return(previous.data+current.data) /2

        • previous := current

        • current := current.right

示例

让我们看看下面的实现以便更好地理解 −

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
def number_of_nodes(root):
   node_count = 0
   if (root == None):
      return node_count
   current = root
   while (current != None):
      if (current.left == None):
         node_count+=1
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if(previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            node_count += 1
            current = current.right
   return node_count
def calculate_median(root):
   if (root == None):
      return 0
   node_count = number_of_nodes(root)
   count_curr = 0
   current = root
   while (current != None):
      if (current.left == None):
         count_curr += 1
         if (node_count % 2 != 0 and count_curr == (node_count + 1)//2):
            return previous.data
         elif (node_count % 2 == 0 and count_curr == (node_count//2)+1):
            return (previous.data + current.data)//2
         previous = current
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if (previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            previous = previous
            count_curr+= 1
            if (node_count % 2 != 0 and count_curr == (node_count + 1) // 2 ):
               return current.data
            elif (node_count%2 == 0 and count_curr == (node_count // 2) + 1):
               return (previous.data+current.data)//2
            previous = current
            current = current.right
root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)
print(calculate_median(root))

输入

root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)

输出

7

相关文章


有用资源