2020-06-27-PHP 实现计算二叉树中的最大路径和

layout: posttitle: PHP 实现计算二叉树中的最大路径和
subtitle: PHP 实现计算二叉树中的最大路径和
date: 2020-06-27
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 二叉树最大路径和
- 递归

计算二叉树最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]
       1
      / \
     2   3
输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
输出: 42

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

解题思路

对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:

1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径

php 代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxPathSum($root) {
        $this->ans = PHP_INT_MIN;
        $this->oneSideMax($root);
        return $this->ans;
    }
    /**
    * 返回经过root的单边分支最大和， 即Math.max(root, root+left, root+right)
    */
    function oneSideMax($root) {
        if ($root === null) return 0;
        // 计算左边分支最大值，左边分支如果为负数还不如不选择
        $left = max(0, $this->oneSideMax($root->left));
        // 计算右边分支最大值，右边分支如果为负数还不如不选择
        $right = max(0, $this->oneSideMax($root->right));
        // left，root，right 作为路径与历史最大值做比较
        $this->ans = max($this->ans, $left + $right + $root->val);
        // 返回经过root的单边最大分支给上游
        return max($left, $right) + $root->val;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券