本文主要是介绍[力扣 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 二叉树中的最大路径和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!