当前位置： 面试刷题>> 二叉树中的最大路径和(经典算法150题)
### 题目描述
给定一个二叉树，其中每个节点的值都是整数。二叉树中的一条路径被定义为从根节点开始，沿着左子树或右子树，经过一系列节点，直到叶子节点（即没有子节点的节点）为止的路径。路径上所有节点的值之和称为该路径的和。求二叉树中所有路径中的最大路径和。
注意：路径不一定非得经过根节点，但路径上至少包含一个节点。此外，路径上的节点数没有限制，可以是单个节点，也可以是整棵树。
### 示例
给定二叉树：
```
1
/ \
2 -3
```
路径 `1 -> 2` 的和为 3，是最大路径和。
### 解题思路
要解决这个问题，我们需要对每个节点进行后序遍历（左子树 -> 右子树 -> 根节点），并在遍历过程中计算每个节点作为根的子树中的最大单边路径和（只考虑左子树或右子树中的最大路径）。同时，我们需要记录遍历过程中遇到的最大路径和，该路径和可能跨越根节点，也可能不跨越。
### 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 maxPathSum($root) {
global $maxSum;
$maxSum = PHP_INT_MIN;
dfs($root);
return $maxSum;
function dfs($node) {
if ($node === null) return 0;
$leftMax = max(0, dfs($node->left));
$rightMax = max(0, dfs($node->right));
$priceNewPath = $node->val + $leftMax + $rightMax;
$maxSum = max($maxSum, $priceNewPath);
return $node->val + max($leftMax, $rightMax);
}
}
// 使用示例
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(-3);
echo maxPathSum($root); // 输出 3
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
global max_sum
max_sum = float('-inf')
def dfs(node):
if not node:
return 0
left_max = max(dfs(node.left), 0)
right_max = max(dfs(node.right), 0)
price_new_path = node.val + left_max + right_max
nonlocal max_sum
max_sum = max(max_sum, price_new_path)
return node.val + max(left_max, right_max)
dfs(root)
return max_sum
# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(-3)
print(maxPathSum(root)) # 输出 3
```
### 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)
}
let maxSum = -Infinity;
function maxPathSum(root) {
dfs(root);
return maxSum;
function dfs(node) {
if (!node) return 0;
let leftMax = Math.max(dfs(node.left), 0);
let rightMax = Math.max(dfs(node.right), 0);
let priceNewPath = node.val + leftMax + rightMax;
maxSum = Math.max(maxSum, priceNewPath);
return node.val + Math.max(leftMax, rightMax);
}
}
// 使用示例
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(-3);
console.log(maxPathSum(root)); // 输出 3
```
通过这些示例代码，你可以看到如何递归地求解二叉树中的最大路径和。每个示例都采用了全局变量（或闭包）来记录最大路径和，并在后序遍历过程中更新这个值。