【LeetCode热题100】124.二叉树的最大路径和（二叉树）

news/2024/4/29 12:54:48/文章来源:https://blog.csdn.net/OkizukiNanami/article/details/137121349

一.题目要求

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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 * 10⁴]
-1000 <= Node.val <= 1000

四.解题思路

这题在递归讨论情况的时候掉了个坑，看了一下评论区有老哥也提到了，就直接引用了。
在这里插入图片描述
可以再简化一下，不用考虑5，6，因为左右会作为根提前出现

五.代码实现

class Solution {
public:int maxPathSum(TreeNode* root) {dfs(root);return m;}int dfs(TreeNode* root) {if(!root) return -99999;int l = dfs(root->left);int r = dfs(root->right);int lroot = l + root->val;int rroot = r + root->val;int lrroot = l + r + root->val;int val = root->val;int mmax = max(val, max(lrroot, max(lroot, rroot)));if(mmax > m) m = mmax;return max(val, max(lroot, rroot));}
private:int m = INT_MIN;
};