資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用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
459 次檢視
