leetCode ✏Leetcode基础刷题之(124. Binary Tree Maximum Path Sum)
✏描述
给定一棵非空二叉树，求最大路径和。对于这个问题，可以从任意的节点出发，可以不经过根节点，但是至少要经过一个结点。
✏题目实例
✏题目分析
递归，每一次都需要判断左右子树，像例子2根节点为负数的情况，我们当然要舍弃负数，因为无论什么时候正数加负数的值都会变小。所以对于左右子节点，取0和当前结点值的最大值，定义一个全局变量，每次更新全局最大值，也就是把它和left+right+当前结点值比较大小，更新全局最大路径和。还有一点要注意的是，定义初始值的时候并不能直接初始化为0，因为如果二叉树只有一个负数的根节点，题目要求的是至少要经过一个节点，那么结果可想而知。
/**
* @param TreeNode $root
* @return Integer
*/
function maxPathSum($root) {
$res=$root->val;
$this->helper($root,$res);
return $res;
}
function helper($root,&$res)
{
if(!$root) return 0;
$left=max($this->helper($root->left,$res),0);
$right=max($this->helper($root->right,$res),0);
$res=max($res,$left+$right+$root->val);
return max($left,$right)+$root->val;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)