题目描述
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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;
}
};