二叉树中的最大路径和
难度:
标签:
题目描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
代码结果
运行时间: 112 ms, 内存: 22.3 MB
/*
* 思路：
* 1. 使用Java Stream API处理路径和计算。
* 2. 定义一个带有累加器的帮助类，通过流操作获取每个节点的最大路径和。
*/
import java.util.stream.Stream;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return maxSum;
}
private int helper(TreeNode node) {
if (node == null) return 0;
int left = Math.max(helper(node.left), 0);
int right = Math.max(helper(node.right), 0);
int currMaxPath = node.val + left + right;
maxSum = Math.max(maxSum, currMaxPath);
return node.val + Math.max(left, right);
}
}
解释
方法:
这个题解采用了深度优先搜索（DFS）的思路来解决问题。对于每个节点，我们计算以该节点为根的左子树和右子树的最大路径和，然后更新全局变量 m 为当前最大路径和。最后返回经过该节点的单边最大路径和，用于上层递归。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在DFS函数中，为什么要选择返回经过当前节点的单边最大路径和，而不是两边的总和？
▷🦆
当二叉树中包含负数节点时，这个算法是如何处理的？为什么选择忽略负数的子树贡献？
▷🦆
在更新全局变量m时，为什么能保证`m`总是记录下所有可能路径中的最大值？
▷🦆
递归函数中使用了nonlocal关键字修改外层函数的变量m，这种做法有没有可能的替代方案，比如使用类属性或传递参数的方式？
▷相关问题
路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
求根节点到叶节点数字之和
给你一个二叉树的根节点
root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径1->2代表数字12从根到叶子节点路径1->3代表数字13因此，数字总和 = 12 + 13 =25
示例 2：
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径4->9->5代表数字 495 从根到叶子节点路径4->9->1代表数字 491 从根到叶子节点路径4->0代表数字 40 因此，数字总和 = 495 + 491 + 40 =1026
提示：
- 树中节点的数目在范围
[1, 1000]内 0 <= Node.val <= 9- 树的深度不超过
10
