mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
41 lines
1.3 KiB
Markdown
Executable File
41 lines
1.3 KiB
Markdown
Executable File
# [124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given a **non-empty** binary tree, find the maximum path sum.
|
||
|
||
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain **at least one node** and does not need to go through the root.
|
||
|
||
**Example 1:**
|
||
|
||
Input: [1,2,3]
|
||
|
||
1
|
||
/ \
|
||
2 3
|
||
|
||
Output: 6
|
||
|
||
**Example 2:**
|
||
|
||
Input: [-10,9,20,null,null,15,7]
|
||
|
||
-10
|
||
/ \
|
||
9 20
|
||
/ \
|
||
15 7
|
||
|
||
Output: 42
|
||
|
||
## 题目大意
|
||
|
||
给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
|
||
|
||
## 解题思路
|
||
|
||
- 给出一个二叉树，要求找一条路径使得路径的和是最大的。
|
||
- 这一题思路比较简单，递归维护最大值即可。不过需要比较的对象比较多。`maxPathSum(root) = max(maxPathSum(root.Left), maxPathSum(root.Right), maxPathSumFrom(root.Left) (if>0) + maxPathSumFrom(root.Right) (if>0) + root.Val)` ，其中，`maxPathSumFrom(root) = max(maxPathSumFrom(root.Left), maxPathSumFrom(root.Right)) + root.Val`
|
||
|