力扣124. 二叉树中的最大路径和（树形DP）
本题和周赛最后一题类似，都是树形DP的问题
最优路径可以从两个地方得到，一个是经过根节点时，左子树最优+右子树最优+根节点；另一个是转化为子问题，将左右子树分别作为根节点来求解；
难点在于递归的返回值和答案之间的关系；
关于此类问题，一般是开一个全局变量来存储和更新答案；dfs只返回需要的值；
在本题中，需要dfs返回的是该子树和根节点相连情况下的单条路径最优值；
在计算过程中，更新答案为左右两边单条路径最优解+根节点组合为满足要求的路径；
class Solution {private:int ans = -1e6;public:int getmax(TreeNode* root) {if(root == nullptr) return 0;int l = getmax(root->left), r = getmax(root->right);int res = root->val + max({l, r, 0});ans = max({ans, root->val + l + r, res});return res;}int maxPathSum(TreeNode* root) {getmax(root);return ans;}};