二叉樹中節點之間的距離？

這必須是一個遞歸算法二叉樹中節點之間的距離？

dis(tree, x, y) < --function呼叫 X & y是節點

每個遞歸調用返回（DX，DY，DXY） dx是X DY的深度爲深度Ÿ DXY是相互

我用最低的共同祖先思想的距離，但是，這並不適合這種格式（沒有全局變量）。

來源

2012-06-18 user1419501

你的問題是什麼？ –

只需要知道每個堆棧幀需要做什麼 – user1419501

爲什麼LCA需要全局變量？另外，你確定LCA能幫助你嗎？ – templatetypedef

這必須是一個遞歸算法

我假設你的意思是作爲你想要的答案約束（有重複的解決方案）。遞歸（功能）解決方案如下：

dis(tree, x, x) = 0 

dis(tree, x, NULL) = INF 
dis(tree, NULL, x) = INF 

dis(tree, x, y) = min(dis(tree, parent(x), y)+1, dis(tree, x, parent(y))+1)

來源

2012-06-18 21:24:58

如果樹是雙向鏈接，你可以做從節點廣度優先搜索X搜索節點Y。

來源

2012-06-18 21:26:29

你只需要找到共同的祖先，所以只需要搜索（logN）祖先列表，不需要BFS。 –

是的，你說得對。在大多數情況下，尋找共同的祖先比BFS要快得多。我很抱歉。 –

二叉樹中節點之間的距離？

回答

相關問題