[力扣 Hot100]Day50 二叉树中的最大路径和

本文主要是介绍[力扣 Hot100]Day50 二叉树中的最大路径和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 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->left&&root->right&&root->left->val>0&&root->right->val>0){if(root->val+root->left->val+root->right->val>max_val)max_val=root->val+root->left->val+root->right->val;root->val=root->val+(max(max(root->left->val,root->right->val),0));return;}if(root->left&&root->left->val>0)root->val+=root->left->val;if(root->right&&root->right->val>0)root->val+=root->right->val;if(root->val>max_val)max_val=root->val;}int maxPathSum(TreeNode* root) {int max_val=-1001;acc_h(root,max_val);return max_val;}
};

这篇关于[力扣 Hot100]Day50 二叉树中的最大路径和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---