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

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

所以，如果输入如下：

那么输出将是7

为了解决这个问题，我们将遵循以下步骤：

  • 如果根节点为空，则

    • 返回0

  • node_count := 树中节点的数量

  • count_curr := 0

  • current := 根节点

  • 当current不为空时，执行：

    • 如果current.left为空，则

      • count_curr := count_curr + 1

      • 如果node_count模2不等于0，且count_curr等于(node_count + 1) /2，则

        • 返回previous.data

      • 否则，如果node_count模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模2不等于0，且count_curr等于(node_count + 1) / 2，则

          • 返回current.data

        • 否则，如果node_count模2等于0，且count_curr等于(node_count / 2) + 1，则

          • 返回(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

更新于：2020年8月25日

459 次查看

启动您的职业生涯

完成课程获得认证

开始学习
广告