当前位置： 面试刷题>> 最大子树 (经典算法题500道)
### 题目描述补充
**题目：最大子树和**
给定一棵二叉树，每个节点包含一个整数值。找出这棵树中节点值之和最大的子树，并返回这个最大和。
**注意**：
1. 子树是指由树中的一个节点（包括这个节点本身）以及这个节点的所有后代节点所构成的树。
2. 空树或者只包含一个节点的树也被视为有效子树。
### 示例
给定以下二叉树：
```
1
/ \
2 -3
/ \ \
2 2 -3
```
返回值为 6，因为子树 `[2, 2]` 的和最大，为 6。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课**网站中有更多关于算法和数据结构的内容分享给大家学习，可以帮助你深入理解并掌握相关知识。