トピック：
バイナリツリーの最大パス合計
バイナリツリーが与えられた場合、最大パス合計を見つけます。
パスは、ツリー内の任意のノードで開始および終了する場合があります。
例えば：
以下のバイナリツリーを考えると、
1 / / 2 3
戻る6。
ノードは負である可能性があり、最もパスを探して、通過するノードが最大になるようにします。パスは任意のノードで開始および終了できますが、戻ることはできません。
この質問は珍しいように見えますが、それについて考えると、それはバイナリツリーの横断と単純な動的計画のアイデアにすぎないことがわかります。
問題を分離することができます。最後の最大のパスがルートノードを通過しない場合でも、独自の「最高点」が必要です。したがって、すべてのノードを見つける必要があります。パスがこのノードを「最高点」として取る場合、パスの最大長はどれくらいですか？マックスとして注意してください。次に、最大値の最大値を見つけます。これがあなたが探している結果です。 「整数シーケンスで最大の連続サブシーケンスを見つける」と同じアイデア。
以下は、各「最高点」に対応するMax間の関係を見つけるためです。
ルートノードを例として見てみましょう。ルートノードを通過する最大パスの計算方法は次のとおりです。
左の子が出発点として左のサブツリーの最大パス長aと、右サブツリーの最大パス長bが出発点として右子を持つことがわかります。次に、この点のmax = max（a+b+node.val、a+node.val、b+node.val、node.val）
したがって、上記のAまたはBを計算する関数を定義します。そのパラメーターはノードであり、その戻り値は最大パス長です。ただし、このパスの開始点は入力ノードでなければならず、パスはルートノードとして開始点を持つサブツリー上にある必要があります。
次に、関数func（node）の戻り値は次のように定義できます。returnmax（func（node.left）+node.val、func（node.right）+node.val、node.val）
終了条件はnode == nullであり、0を直接返します。
次に、最大計算とmaxの計算の上記のプロセスを完全にFUNC（ノード）に入れることができることがわかりました。
このアイデアのコードによると、Maxpathsumcoreは上記のFUNC（ノード）の実装です。
/** *バイナリツリーの定義 * struct treeNode { * int val; * treenode *左; * treenode *右; * treenode（int x）：val（x）、left（null）、右（null）{} *}; */class solution {public：int maxpathsum（treenode *root）{maxpathsumcore（root）; return max;} int maxpathsumcore（treenode *node）{if（null == node）return 0; int a = maxpathsumcore（node-> left）;右）; if（（a+b+node-> val）> max）max =（a+b+node-> val）; if（（a+node-> val）> max）max =（a+node-> val）; if（（b+node-> val）> max =（b+node-> val） maxviathisnode =（（a + node-> val）> node-> val？（a + node-> val）：note-> val）; return（maxviathisnode>（b + node-> val）？maxviathisnode：（b + node-> val））;} int max = -999999;};時間の複雑さo（n）、nはノードの総数です。
要約します
上記は、Javaプログラミングのバイナリツリーの最大パスのコード分析に関するこの記事の内容全体です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました！