一千萬個為什麽

搜索

在有限內存的二叉樹中查找第一個空值

我有一個二叉樹,每個節點可以有一個值。

我想在樹中找到值為null並且最接近根的節點。如果有兩個距離根的距離相同的節點,則可以這樣做。我需要盡量減少對二叉樹的讀訪問次數。假設工作記憶僅限於k個節點。

深度k的DFS是詳盡無遺的,但是除非我首先遍歷整棵樹,否則不會找到最接近的節點。 BFS會找到最接近的,但可能會失敗,因為DFS可以找到更深的空值,並使用相同的內存。

我希望有最少數量的讀取訪問樹並找到最接近的空節點。

(我最終也需要在n-tree中實現這個功能,所以一個通用的解決方案會很好,沒有對樹的寫入權限,只需閱讀。)

最佳答案

我將通過簡單的樹修剪來實現DFS。因此,您不得不運行整個樹。例如,如果您在高度h找到空值,您可以跳過節點,它們處於相同或更深的位置。

轉載註明原文: 在有限內存的二叉樹中查找第一個空值