PHP 实现计算二叉树中的最大路径和

PHP 实现计算二叉树中的最大路径和

author: he xiaodong date: 2020-06-27
计算二叉树最大路径和

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

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

示例 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;
    }
}

顺带推荐买课,用右侧链接有优惠 算法面试通关40讲