binary-tree-maximum-path-sum

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node&#39;s values in the path.

Given the <code>root</code> of a binary tree, return the maximum path sum of any non-empty path.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg" style="width: 322px; height: 182px;" />
<pre>
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -&gt; 1 -&gt; 3 with a path sum of 2 + 1 + 3 = 6.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg" />
<pre>
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -&gt; 20 -&gt; 7 with a path sum of 15 + 20 + 7 = 42.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 3 * 104]</code>.</li>
	<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>
</ul>

maxPathSum

Binary Tree Maximum Path Sum

Path Sum

path-sum

路径总和

Sum Root to Leaf Numbers

sum-root-to-leaf-numbers

求根节点到叶节点数字之和

Path Sum IV

path-sum-iv

路径总和 IV

Longest Univalue Path

longest-univalue-path

最长同值路径

Time Needed to Inform All Employees

time-needed-to-inform-all-employees

通知所有员工所需的时间

Difference Between Maximum and Minimum Price Sum

difference-between-maximum-and-minimum-price-sum

最大价值和与最小价值和的差值

Tree

Depth-First Search

Dynamic Programming

Binary Tree

&#20108;&#21449;&#26641;&#20013;&#30340; &#36335;&#24452; &#34987;&#23450;&#20041;&#20026;&#19968;&#26465;&#33410;&#28857;&#24207;&#21015;&#65292;&#24207;&#21015;&#20013;&#27599;&#23545;&#30456;&#37051;&#33410;&#28857;&#20043;&#38388;&#37117;&#23384;&#22312;&#19968;&#26465;&#36793;&#12290;&#21516;&#19968;&#20010;&#33410;&#28857;&#22312;&#19968;&#26465;&#36335;&#24452;&#24207;&#21015;&#20013; &#33267;&#22810;&#20986;&#29616;&#19968;&#27425; &#12290;&#35813;&#36335;&#24452; &#33267;&#23569;&#21253;&#21547;&#19968;&#20010; &#33410;&#28857;&#65292;&#19988;&#19981;&#19968;&#23450;&#32463;&#36807;&#26681;&#33410;&#28857;&#12290;

&#36335;&#24452;&#21644; &#26159;&#36335;&#24452;&#20013;&#21508;&#33410;&#28857;&#20540;&#30340;&#24635;&#21644;&#12290;

&#32473;&#20320;&#19968;&#20010;&#20108;&#21449;&#26641;&#30340;&#26681;&#33410;&#28857; <code>root</code> &#65292;&#36820;&#22238;&#20854; &#26368;&#22823;&#36335;&#24452;&#21644; &#12290;

&nbsp;

&#31034;&#20363; 1&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg" style="width: 322px; height: 182px;" />
<pre>
&#36755;&#20837;&#65306;root = [1,2,3]
&#36755;&#20986;&#65306;6
&#35299;&#37322;&#65306;&#26368;&#20248;&#36335;&#24452;&#26159; 2 -&gt; 1 -&gt; 3 &#65292;&#36335;&#24452;&#21644;&#20026; 2 + 1 + 3 = 6</pre>

&#31034;&#20363; 2&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg" />
<pre>
&#36755;&#20837;&#65306;root = [-10,9,20,null,null,15,7]
&#36755;&#20986;&#65306;42
&#35299;&#37322;&#65306;&#26368;&#20248;&#36335;&#24452;&#26159; 15 -&gt; 20 -&gt; 7 &#65292;&#36335;&#24452;&#21644;&#20026; 15 + 20 + 7 = 42
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li>&#26641;&#20013;&#33410;&#28857;&#25968;&#30446;&#33539;&#22260;&#26159; <code>[1, 3 * 104]</code></li>
	<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>
</ul>

&#20108;&#21449;&#26641;&#20013;&#30340;&#26368;&#22823;&#36335;&#24452;&#21644;

Sunbelt Computer Software

PL/B Language Development and Support