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

Question

这一定是递归算法

dis(tree, x, y)<--函数调用 x & y 是节点

每个递归调用返回 (dx, dy, dxy) dx 是 x 的深度 dy 是 y 的深度 dxy 是彼此之间的距离

我正在考虑使用最低的共同祖先，但这不适合这种格式（没有全局变量）。

Answer 1

这一定是递归算法

我假设您的意思是对您想要的答案的限制（有迭代解决方案）。递归（函数式）解决方案如下：

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)

Answer 2

如果树是双向链接的，您可以从节点 x 搜索节点 y 进行广度优先搜索。