0

-ve と +ve の値を持つバイナリ ツリーが与えられます。すべてのパスのルートから任意のノードへの最大合計を出力します。O(n) で実行します。ツリーの 1 回のトラバーサルのみ。

努力:) 1) http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/ はまったく別の問題です。

2) O(n) + O(n) は受け付けません。

私のアプローチ。

1)

i) 可能な最大合計を見つけます。ii) 現在の path と sum を維持しながら preorder をトラバースします。if(curr_sum == max_sum) 印刷パス。

2) i) 可能な最大合計を見つけます。ii) 現在の path と sum を維持しながら preorder をトラバースします。if(curr_sum == max_sum) 印刷パス。このノードのアドレスもノード配列 Arr に保存します。次回 curr_sum==max_sum の場合、パスが既に印刷されている場合は Arr[] をチェックインするだけです

問題：これにより、いくつかのパスが複数回出力されます。以上のインタビュアーは 1 つのトラバーサルを望んでいました。最大合計を見つけるには 2.1 が必要です。その他のパスを印刷します。

4

1 に答える 1

2

ツリーで深さ優先検索を実行し、すべてのサブパスの合計を計算し、それらを同じ長さのサブパスを含むリストの並べ替えられた配列に格納します。これは O(n) で実行でき、グラフを 1 回トラバースすることは簡単にわかります。

結果は、 length のパスのリストを含む配列aになります。最大のインデックスを記録し、最終的にリスト内のすべてのパスを出力します。a[i]ija[j]

于 2013-01-19T09:42:51.457 に答える