124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]1/ \2 3输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]-10/ \9 20/ \15 7输出: 42
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxPathSum(TreeNode* root) {int val=INT_MIN;dfs(root,val);return val==INT_MIN? 0:val;}int dfs(TreeNode* root, int &val){if (root == nullptr) return 0;int left = dfs(root->left, val); //左儿子的最长路径和int right = dfs(root->right, val); //右儿子的最长路径和int lmr = root->val + max(0, left) + max(0, right); //root节点作为经过点int ret = root->val + max(0, max(left, right)); //root节点作为起始点val = max(val, max(lmr, ret));return ret;}
};