文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / binary-tree-maximum-path-sum
文件大小:
1.30 KB
下载地址:
文本预览:
## What will the maximum path look like
Though paths can be starting from any node and end at any node, the appearances only can be:
* Appearance 1
```
*
/ \
* *
/ \
* *
/ \
S *
\
E
```
* Appearance 2
```
E
/
*
/
*
/
S
```
* Appearance 3
```
S
\
*
\
*
\
*
\
E
```
### Note
Appearances above are only talking about `TRUNK`.
Treat the path below as Appearance 1
```
*
/ \
* *
/ \
* *
\ /
S *
\
E
```
## Tree Version of [Maximum Subarray](../maximum-subarray)
* Appearance 2/3
These two appearances are easy to understand and to build a path, just take the maximum node.
like `Maximum Subarray`, if the sum goes below `0`, forget the old nodes.
* Appearance 1
If a node's left child or right child is less than `0`, drop it, then the node becomes `Appearance 2/3`.
If both the left child and right child are positive, just add them together, `maxPathSum(node.left) + node.val + maxPathSum(node.right)` will be the `maxPathSum` which contains that node.
## Put them together
As we know how to find the `maxPathSum` of any node, we can go through the tree and update the max value.
Though paths can be starting from any node and end at any node, the appearances only can be:
* Appearance 1
```
*
/ \
* *
/ \
* *
/ \
S *
\
E
```
* Appearance 2
```
E
/
*
/
*
/
S
```
* Appearance 3
```
S
\
*
\
*
\
*
\
E
```
### Note
Appearances above are only talking about `TRUNK`.
Treat the path below as Appearance 1
```
*
/ \
* *
/ \
* *
\ /
S *
\
E
```
## Tree Version of [Maximum Subarray](../maximum-subarray)
* Appearance 2/3
These two appearances are easy to understand and to build a path, just take the maximum node.
like `Maximum Subarray`, if the sum goes below `0`, forget the old nodes.
* Appearance 1
If a node's left child or right child is less than `0`, drop it, then the node becomes `Appearance 2/3`.
If both the left child and right child are positive, just add them together, `maxPathSum(node.left) + node.val + maxPathSum(node.right)` will be the `maxPathSum` which contains that node.
## Put them together
As we know how to find the `maxPathSum` of any node, we can go through the tree and update the max value.
点赞
回复
X