3

ルートが座標 (x,y) を持つ座標平面のバイナリ ツリーが与えられます。このツリーの x 軸上の最大射影を見つける必要があります。つまり、基本的に、このツリーの最大幅を見つける必要があります。ツリーも歪んでいる可能性があります。

例:

    1
   / \
  2   3
 /   / \
4   5   6

Width = 5

    1
   / \
  2   3
 /  
4

Width = 4

    1
   / 
  2  
 /   
4

Width = 3

私のロジックは、基本的に左端のノードと右端のノードを見つけて、それらの x 座標を減算することでした。ルートから左の部分木に行くと にxなりx-1、 y になりy+1、右の部分木に行くと にxなりx+1ます。これら 2 つの座標 xLeft と xRight を見つけると、最大幅を見つけることができます。しかし、私はそれをコーディングするのに苦労しました。

誰もがそれについて行く方法を教えてもらえますか? 宿題ではありませんが、どこかで読んだプログラミングのパズルです。

4

2 に答える 2

1

これはレベル順の走査問題です。レベル順にツリーをトラバースするときに、最大レベルの幅を追跡します。完了すると、そのレベルの左端のノードと右端のノードが、探している最終的な投影を提供します。

編集：

mbeckish：上記の解決策は、質問が最大の断面に関するものであると想定しています。ただし、そうでない場合でも、レベルの順序は機能します。コードがトラバーサル中とトラバーサル中の両方minXを追跡する必要があることを除いてmaxX。minX左端のノードをmaxX追跡し、右端のノードを追跡します。その場合、答えはになりますmaxX-minX+1。

このサイトには、変更可能な十分に文書化されたbstトラバーサルコードが多数あります。

于 2013-01-18T15:06:26.017 に答える
0

これは、現在のノードのx座標を維持しながら、標準のツリートラバーサルアルゴリズムを実行することで解決できます。左に行くときはいつでもxをデクリメントし、右に行くときはいつでもxをデクリメントします。これはここに示されています：

void ExtremalNodes(Node* curr, int x, int& maxX, int& minX) {
    if (curr == nullptr) return;
    maxX = std::max(x, maxX);
    minX = std::min(x, minY);
    ExtremalNodes(curr->left, x - 1, maxX, minX);
    ExtremalNodes(curr->right, x + 1, maxX, minX);
}
int TreeProjection(Node* root) {
    if (root == nullptr) return 0;

    int maxX = 0;
    int minX = 0;
    ExtremalNodes(root, 0, maxX, minX);
    return maxX - minX + 1;
}

お役に立てれば！

于 2013-01-18T17:15:29.070 に答える