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 を検索する幅優先検索を実行できます。