[二叉树]leetcode124：二叉树中的最大路径和(hard)

二叉树]leetcode124：二叉树中的最大路径和(hard)"/>

[二叉树]leetcode124：二叉树中的最大路径和(hard)

题目：

124. 二叉树中的最大路径和

题解：

• 递归
• 对于任意一个节点，如果最大路径包含该节点，那么只可能有两种情况：
• 1、其左右子树中所构成的和路径值较大的加上该节点的值向父节点回溯构成最大路径
• 2、左右子树都在最大路径中，加上该节点的值构成了最终的最大路径

代码如下：

class Solution {
public:int res=-3e7-10;int maxPathSum(TreeNode* root) {dfs(root);return res;}int dfs(TreeNode* root){if(!root)return 0;// 递归求左右子树中的路径的最大值int l=max(dfs(root->left),0),r=max(dfs(root->right),0);// 更新最长直径res=max(res,root->val+l+r);// 递归边界是从节点x到左子树或者右子树中路径的最大值return max(l,r)+root->val;}
};