查找BST中每個級別的最大元素

-1

[1] In O(n) time and O(1) space 
[2] In O(logn) time and O(n) space

編輯：發表@Imposter解決方案的工作罰款[1] 這裏是[1]

private int level = 0; 
private int VisitedLevels = -1; 

public void findLargestByLevel(AvlNode root) 
{ 
    if(root == null) return; 

    else 
    { 
     if(level > VisitedLevels) 
     { 
      System.out.println(root.data + " @ Level = " + level); 
      VisitedLevels++; 
     } 
     level++; 

     findLargestByLevel(root.right); 
     findLargestByLevel(root.left); 

     level--; 
    } 
}

的解決方案，但我還是沒能制定出一個解決方案[ 2]

，我已經想好了辦法：如果我們預處理樹和扁平像樹的系列化，

    100 
      50   200 
     20  75 

#L0, 100, #L1, 50, 200, #L2, 20, 75, #L3

凡#L是水平的標誌：

那麼我們可以很容易地回答水平最高和最低的O（1）時間查詢，此外，如果樹得到改進，我們可以進行插入和在LogN時間從序列化數據中刪除。請爲[2]建議某人，儘管在我看來zit看起來不可能實現[2]，但我希望聽到其他人的建議

來源

2012-09-21 Astric Star

看起來像功課，不是嗎？沒有一些預處理[2]是不可能的（如果你嘗試在O（log n）中找到填充O（n）個存儲單元的算法，註定會失敗）。 – KCH

很好。什麼試過了？已經諮詢了哪些資源？ – 2012-09-21 00:41:15

如果我不這樣做？ ;） – MAK

如果BST是完整的BST，那麼它可以在log（N）時間內完成，因爲你所需要做的就是始終向右遍歷（因爲右側的元素總是比左側更粗糙）。如果它不是完整的BST，那麼我們必須遍歷所有的元素，因爲我們不確定右子樹的高度總是大於左子樹。

例如：如果右子樹有兩層，左子樹有三層，那麼使用上面的方法，我們可以打印最大值直到兩層，但是我們遺漏了右子樹中不存在的第三層。

因此，如果不是Full BST，那麼時間複雜度將是最小的O（n），如果沒有給出額外的空間，時間複雜度可能會更大。

如果您使用BFS，它只需要O（n）時間複雜度和O（n）空間複雜度。如果你想使用DFS，那麼下面的算法會幫助你處理O（n）的時間複雜度，而O（h）其中h是樹的高度。

帶全局變量計數器它指示在遍歷時到目前爲止的最大級數。

取兩個變量大號和[R當過您對左子樹增量遞歸調用大號

同樣，當你永遠讓右子樹增量[R遞歸調用。

查找最大值L和R爲每個節點提供級別號碼。

當曾經有增量在最大（L，R），用於在穿過檢查這與計數器如果計數器小於MAX（L，R）的節點然後分配內存和intialize到零和增量計數器。（這意味着我們實際上爲樹中的每個級別創建變量）。

在遍歷我們將檢查每一次高度和水平變化，並與如果存在節點比級變量更大然後更新與正在考慮的節點級變量被認爲是當前節點進行比較。

遍歷後打印高度或水平變量。

來源

2012-09-21 06:45:38 Imposter

問題的最差解決方案我編輯了問題發佈答案[1] –

-1

[1]這可以通過迭代地完成每個級別並保持記錄最大。這可以通過一個簡單的BFS來完成（假設您在存儲中也不計算遞歸級別變量）。例如。一個簡單隊列取代的遞歸將比O（1）存儲花費更多，在這種情況下，除非節點按級別進行排序，否則這對我來說似乎是不可能的。

[2]二叉樹的右邊孩子的屬性大於左邊，所以如果你每次只是遍歷最右邊的孩子（除非它不存在，那麼帶左邊的孩子），你可以得到log（n ）時間。我不確定它是否需要O（n）存儲。

來源

2012-09-21 05:29:26 FUD

點[2]中提到，將無法正常工作，如果BST是左重：一裝置，如果給定的BST的左子樹具有比其右子樹更高度，剛鍛鍊的示例 –

BFS是O（N）的空間和O （n）的時間，...所以它似乎是在給定的要求在 –

查找BST中每個級別的最大元素

回答

相關問題