牛客对应题目链接：二叉树中的最大路径和_牛客题霸_牛客网
力扣对应题目链接：124. 二叉树中的最大路径和 - 力扣（LeetCode）
一、分析题目
树形 dp ：
- 左子树收集：以左子树为起点的最大单链和。
- 右子树收集：以右子树为起点的最大单链和。
- 根节点要做的事情：整合左右子树的信息，得到经过根节点的最大路径和。
- 向上返回：以根节点为起点的最⼤单链和。
二、代码
//值得学习的代码 class Solution { public: int ret = -1010; int maxPathSum(TreeNode* root) { dfs(root); return ret; } int dfs(TreeNode* root) { if(root == nullptr) return 0; int l = max(0, dfs(root->left));// 左⼦树的最⼤单链和 int r = max(0, dfs(root->right)); // 右⼦树的最⼤单链和 // 经过root的最⼤路径和 ret = max(ret, root->val + l + r); return root->val + max(l, r); } }; //力扣AC代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: int maxSum=INT_MIN; public: int maxGain(TreeNode* node) { if(node==nullptr) return 0; int leftGain=max(0, maxGain(node->left)); int rightGain=max(0, maxGain(node->right)); int sum=leftGain+rightGain+node->val; maxSum=max(maxSum, sum); return node->val+max(leftGain, rightGain); } int maxPathSum(TreeNode* root) { maxGain(root); return maxSum; } };
