在 Python 中,在 O(n) 时间和 O(1) 空间内查找 BST 的中位数
假设我们有二叉搜索树 (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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

