最新国际新闻 大事件,seo搜索引擎优化方法,美食网站开发开题报告,网站logo怎么做最清楚题目描述
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。 出处
思路
DFS寻找左右子树的最长路径然后看看相加能否变得更大。
代码
class Solution {
public:void acc_h(TreeNode* root,int max_val){if(root-left) acc_h(root-left,max_val);if(root-right) acc_h(root-right,max_val);if(root-leftroot-rightroot-left-val0root-right-val0){if(root-valroot-left-valroot-right-valmax_val)max_valroot-valroot-left-valroot-right-val;root-valroot-val(max(max(root-left-val,root-right-val),0));return;}if(root-leftroot-left-val0)root-valroot-left-val;if(root-rightroot-right-val0)root-valroot-right-val;if(root-valmax_val)max_valroot-val;}int maxPathSum(TreeNode* root) {int max_val-1001;acc_h(root,max_val);return max_val;}
};
