ツリーの直径を見つける - c ++、アルゴリズム、ツリー

私はバイナリツリーの直径を見つけるためのコードを書いています。しかし、どこが間違っているのか分かりません。私が書いた2つの関数とその定義は以下の通りです：

    int btree::diameteroftree(node* leaf)
{
if (leaf==NULL)
return 0;

int lheight = hieghtoftree(leaf->left);
int rheight = hieghtoftree(leaf->right);

int ldiameter = diameteroftree(leaf->left);
int rdiameter = diameteroftree(leaf->right);

return max(lheight + rheight + 1,max(ldiameter,rdiameter));
}


int btree::hieghtoftree(node* leaf)
{
int left=0,right=0;
if(leaf==NULL)
return -1;
else
{
left=hieghtoftree(leaf->left);
right=hieghtoftree(leaf->right);
if(left > right)
return left +1;
else
return right+1;
}
}

ここでどこが間違っているのか分かりません。誰かが私に知らせることができます...

回答：

回答№1は1

最長のパスにあるノードの数を返したいとします。したがって、あなたのアルゴリズムの問​​題はこの行です：

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

どこで

rootDiameter = lheight + rheight + 1

最も深いノードからのパスの長さ左のツリーの右のツリーの最も深いノードに移動します。ただし、この計算は正しくありません。単一ノードは高さ0を返すので、カウントされません。あなたには2つの選択肢があります：

1. 変化する hieghtoftree "ホップ"の数ではなく、最も深いパス上のノードの数を返す
2. あなたの合計でこの問題に対処する

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));

---

回答№2の場合は0

有向ルートツリーでは、ノードのペアの間に常に最大で1つのパスが存在し、どのノードへの最長パスも常にルートから始まります。それは、 直径 単純に木全体の高さです height(root)これは再帰で計算することができます

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

EDIT：あなたがコメントにリンクしているページは、 無向 木。別のツリー表現が必要です（例：隣接行列。

---

回答№3の場合は0

ルートRと2つの葉L1、L2を持つ3ノードのツリーを考えてみましょう。次に、heightoftree（L1）== heightoftree（L2）== -1。従って、Diameteroftree（R）は（-1）+（ - 1）+1 = -1である。

私はリターン-1をお勧めします。 - > 0を返します。 そして 戻り値max（lheight + rheight + 1、max（ldiameter、rdiameter））; - >戻り値max（lheight + rheight + 2、max（ldiameter、rdiameter））;

結果は、パス上のエッジの数になります。ノードの数を数える場合は、必要に応じて最終結果から1つを減算するか、または減算します。

---