二叉树中节点之间的距离？

这必须是一个递归算法二叉树中节点之间的距离？

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要快得多。我很抱歉。 –

二叉树中节点之间的距离？

回答

相关问题