查找二叉樹中節點的深度不是BST

我有一個二叉樹而不是bst，我需要找到該二叉樹中某個節點的深度有沒有其他方法可以實現除了使用某些稀釋度計的水平順序遍歷以主要計數水平。查找二叉樹中節點的深度不是BST

作爲輸入，我有樹的根節點和我需要找到深度的樹的節點之一。

我希望有一些遞歸的方式來找到這個

來源

2011-11-23 Ashish Sharma

家庭作業問題？ –

如果你不想做一個BFS你可以做一個DFS（你也可以做到這一點遞歸）。

來源

2011-11-23 18:40:47

可以請你給我一些示例代碼使用遞歸來找到這個.. –

由於你的問題似乎真的是一個家庭作業的問題，我強烈建議你看看你最喜歡的搜索引擎如何DFS的作品。 –

由於樹不是BST，最壞的複雜度將是O（n）。因此，任何類型的遍歷（pre，post，in）都會幫助您將當前節點與輸入節點進行比較。所有這些遍歷都使用遞歸。 –

嘗試在遞歸函數中傳遞一個附加參數來指示深度。

來源

2011-11-24 07:33:54 kaustubh

不需要額外的參數，您可以簡單地使用函數的返回值。 –

DFS函數的僞代碼，第一次調用將是DFS(root)。

DFS(node v, integer d) 
    visited[v] = true 
    depth[v] = d 

    for each u such that u is adjacent to v 
    if visited[u] == false 
     DFS(u, d+1)

來源

2011-11-24 10:08:33

您不需要訪問（非循環）也不需要深度變量（因爲您只需查找一個值，不需要遍歷每個節點）。 –

查找二叉樹中節點的深度不是BST

回答

相關問題