Leetcode基础刷题之PHP解析(124. Binary Tree Maximum Path Sum)

2019-8-14 星期三 开始吧

上一题链接117. Populating Next Right Pointers in Each Node II

题目描述

给定一棵非空二叉树，求最大路径和。对于这个问题，可以从任意的节点出发，可以不经过根节点，但是至少要经过一个结点。

题目分析

递归，每一次都需要判断左右子树，像例子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;
    }