花時間總結二叉搜索樹中位於兩個數字之間的所有數字

Question

假設我們有一個平衡二叉搜索樹T，它包含n個數字。我們給出兩個 數字L和H，並希望總結T中位於L和H之間的所有數字。假設 T.中有m個這樣的數字。有人可以解釋如何計算所花時間的絕對值計算總和..？

Answer 1

我會留給你弄清楚全部細節，但這裏有一個開始。該算法將執行：

1. 查找樹中大於L的最小數字。你可以在日誌時間內做到這一點。
2. 步行樹，每次移動到下一個最大，並將其添加到運行總數。
3. 當您達到至少H的數字時停止。

我認爲「之間的謊言」的意思是「嚴格間」，但你可能要在步驟1和3