题目描述补充

题目：最大子树和

给定一棵二叉树，每个节点包含一个整数值。找出这棵树中节点值之和最大的子树，并返回这个最大和。

注意：

1. 子树是指由树中的一个节点（包括这个节点本身）以及这个节点的所有后代节点所构成的树。
2. 空树或者只包含一个节点的树也被视为有效子树。

示例

给定以下二叉树：

    1
   / \
  2  -3
 / \   \ 
2   2  -3

返回值为 6，因为子树 [2, 2] 的和最大，为 6。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function maxSubtreeSum($root) {
    $globalMax = PHP_INT_MIN;
    findMaxSubtreeSum($root, $globalMax);
    return $globalMax;
}

function findMaxSubtreeSum($node, &$globalMax) {
    if ($node == null) {
        return 0;
    }
    
    $leftSum = max(0, findMaxSubtreeSum($node->left, $globalMax));
    $rightSum = max(0, findMaxSubtreeSum($node->right, $globalMax));
    
    $currentSum = $leftSum + $rightSum + $node->val;
    $globalMax = max($globalMax, $currentSum);
    
    return $currentSum;
}

// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(-3);
$root->left->left = new TreeNode(2);
$root->left->right = new TreeNode(2);
$root->right->right = new TreeNode(-3);

echo maxSubtreeSum($root);  // 输出 6

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxSubtreeSum(root):
    global_max = float('-inf')
    def findMaxSubtreeSum(node):
        nonlocal global_max
        if not node:
            return 0
        
        left_sum = max(findMaxSubtreeSum(node.left), 0)
        right_sum = max(findMaxSubtreeSum(node.right), 0)
        
        current_sum = left_sum + right_sum + node.val
        global_max = max(global_max, current_sum)
        
        return current_sum
    
    findMaxSubtreeSum(root)
    return global_max

# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(-3)
root.left.left = TreeNode(2)
root.left.right = TreeNode(2)
root.right.right = TreeNode(-3)

print(maxSubtreeSum(root))  # 输出 6

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function maxSubtreeSum(root) {
    let globalMax = -Infinity;
    function findMaxSubtreeSum(node) {
        if (!node) return 0;
        
        let leftSum = Math.max(findMaxSubtreeSum(node.left), 0);
        let rightSum = Math.max(findMaxSubtreeSum(node.right), 0);
        
        let currentSum = leftSum + rightSum + node.val;
        globalMax = Math.max(globalMax, currentSum);
        
        return currentSum;
    }
    
    findMaxSubtreeSum(root);
    return globalMax;
}

// 示例用法
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(-3);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(2);
root.right.right = new TreeNode(-3);

console.log(maxSubtreeSum(root));  // 输出 6

码小课网站中有更多关于算法和数据结构的内容分享给大家学习，可以帮助你深入理解并掌握相关知识。