バイナリツリー内で最も長い連続パスを見つける方法

Question

インタビューでこの質問が尋ねられました。バイナリツリーを考えてみましょう、私たちはそれぞれの要素が1

EGによって異なり、最長パスの長さを印刷する必要があります。

  6 
     / \ 
     5  7 
    /\ /\ 
    2 4 8 9 

答え：5 （4,5,6,7,8 ）

これを行う方法？ 私は、ルートからリーフまで増加するパスを印刷するためにalgoirthmを開発しましたが、私は両方のサブツリーにあるパスを追跡するものを開発していませんでした。

EDIT：変更後に元のツリーを元に戻す必要があります。

Answer 1

1. すべての無効なエッジiを削除します。その差が1より大きい

2. 今、私たちは各フォレストのために、森林を持っている、それが@FilipKočicaに与えられているとして、直径を計算するソリューション

3. Eのエッジが答えは、すべての森林のうち、最大径だろう

Answer 2

サブツリーごとに、サブツリールート、最長減少パスダウン、およびサブツリー内の同じノードからの増減パスからなる最長内部パスまでの最長増加パスを計算できます。

ノードの子をすべて持っていれば、これらのノードを計算するのは簡単です。そのため、後続のトラバーサルの一部として行うことができます。

答えは、ツリー全体で最も長い内部パスです。

Answer 3

あなたの例に示すように、パスに+1の差がなければならないとは限りません。 -1の差は、4 -> 5 -> 4 -> 3 -> 4 -> 5のようなパスになります。

public int getLongestConsecutivePath(TreeNode root) { 
    return root == null 
     ? 0 
     : getLength(root.left, root.value) + getLength(root.right, root.value); 
} 

private int getLength(TreeNode node, int prevVal) { 
    return node == null || Math.abs(node.value - prevVal) > 1 
     ? 0 
     : Math.max(getLength(node.left, node.value), getLength(node.right, node.value)) + 1; 
} 

説明：

• ルートがnullでない場合、我々は左と右のサブツリー内の最大長を取得し、それを合計します。
• サブツリー内の最大長を取得するために、サブツリーの右と左のサブツリーの最大長を再帰的に取得します。
  • 我々は葉に達しているか、我々は、値の差が1以上であるノードに到達した場合、我々は再帰的に左右の部分木から最大長を取得し、1を追加エルス0
  • を返す場合このノード自体に対応するために使用します。
コメントに@qwertymanによって示唆されるように

Answer 4

レッツ同様 longest_asc[a]、からダウン最長1行1下降通路であるlongest_desc[a]

からダウン最長1行1増分パス

固定ルートRの場合、答えはlongest_desc[R] + longest_asc[R] - 1となります。

brut forceソリューションは、各ノードXから2つのdfs/bfsトラバーサルを行い、longest_asc[X] and longest_desc[X]を計算し、それらを一緒にマージします。実行時の複雑さはO(n^2)になります。

しかし、我々は実際に動的なプログラミングを使用して、より良い行うことができます。

longest_asc[X] = max(longest_asc[Y in children[X]] with Y = X + 1) 
longest_desc[X] = max(longest_desc[Y in children[X]] with Y = X - 1) 

はその後、我々は、単一のDFSトラバーサル=>O(n)溶液中のすべての値を計算することができます。