企业怎么做自己的网站,深圳市建设工程交易服务中心网,计算机前景和就业,广州智能建站软件一.题目要求
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root …一.题目要求
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 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
四.解题思路
这题在递归讨论情况的时候掉了个坑看了一下评论区有老哥也提到了就直接引用了。 可以再简化一下不用考虑56因为左右会作为根提前出现
五.代码实现
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;
};六.题目总结
分类讨论什么情况下可以作为最终结果什么情况下可以作为递归返回值二者不是一回事。
