题解 | #二叉树中的最大路径和#

这题叶可以使用一个dfs的方法，遍历的每一个节点的返回值为这条节点即以改节点为根节点，且必须经过该节点的路径的最大值， 当遍历到叶节点的时候直接返回该节点的val， 当遍历的该节点为空时返回0， 当该节点为非叶节点时，这里我们要处理三个数据，分别为该节点本身的数值t_val，其左节点返回的值l_val，其右节点返回的值r_val,将t_vla、t_val+l_val、t_val+r_val和t_val+l_val+r_val的值进行比较，得到最大值max_val，再和事先定义的一个用于存储最终答案变量res进行比较，将res更新为更大的那个值，最后返回max_val即可。

int max_v(int a,int b,int c,int d)
{
    int max=a;
    max=max>b?max:b;
    max=max>c?max:c;
    max=max>d?max:d;
    return max;
}
static int res;
int dfs(struct TreeNode* t)
{
    if(t==NULL)return 0;
    if(t->left==NULL&&t->right==NULL)return t->val;
    int l=dfs(t->left);
    int r=dfs(t->right);
    int max_val=max_v(t->val, t->val+l, t->val+r,t->val+r+l);
    res=res>max_val?res:max_val;
    return max_val;
}
int maxPathSum(struct TreeNode* root ) {
    // write code here
    res=root->val;
    int k=dfs(root);
    res=k>res?k:res;
    return res;
}