水平與大多數節點二叉樹

Question

什麼是找出哪些水平二叉樹（隨機或BST）所需的空間最小量具有節點最多少？

Answer 1

O(1)

遍歷廣度優先搜索方法的BT（二叉樹）。推節點提及它的級別。您將遍歷關卡中的所有節點，然後進入下一關。所以只要保持一個最大變量並不斷更新它。

隊列（用於BST）可能佔用空間O(2^(log(n) -1))。

Answer 2

如果您允許銷燬該樹，那麼您可以在執行樹的bfs時將樹轉換爲鏈表，實質上是模擬樹本身的一個隊列！

您可以找到有關，這裏的信息：Convert a binary tree to linked list, breadth first, constant storage/destructive

這僅需要O(1)空間正如你所重用樹的節點。