二叉树中的最大路径和
题目要求
你需要编写一个算法来找出给定二叉树中任意路径的最大路径和。这里的路径定义为一系列节点，其中每一对相邻节点之间都有一条边连接，且每个节点在路径中只能出现一次。路径不需要从根节点开始，也不需要在叶节点结束，但至少包含一个节点。
解题思路
要解决这个问题，我们可以采用递归的方式，对二叉树进行后序遍历（左-右-根）。在遍历的过程中，我们需要计算两个值：
- 经过当前节点的单边最大路径和（即从当前节点出发，向下延伸到任意节点的最大路径和）。这个值是为了提供给它的父节点计算使用的，因为在父节点看来，它只能从一个子节点接收路径。
- 经过当前节点的最大路径和，这个路径可以不经过父节点，即左子树的路径加上当前节点的值再加上右子树的路径。
对于每个节点，我们需要考虑以下几种情况：
- 当前节点单独构成一条路径。
- 当前节点加上左子树构成一条路径。
- 当前节点加上右子树构成一条路径。
- 当前节点加上左右子树构成一条路径，这种情况下，当前节点是这条路径的最高点。
对于第四种情况，由于路径不能分叉，所以这样的路径不会贡献给父节点的单边最大路径和，但是它可能是全局的最大路径和。
因此，我们需要一个全局变量来记录遍历过程中的最大路径和。在递归函数中，我们计算并返回当前节点作为单边路径的最大和，同时更新全局的最大路径和。
递归的基本步骤如下：
- 如果当前节点为空，返回 0（因为它不贡献任何路径和）。
- 递归计算左子节点的最大单边路径和，如果这个值小于 0，我们就不需要加上左子节点的值，因为它会减小路径和。
- 递归计算右子节点的最大单边路径和，同样地，如果这个值小于 0，我们就不需要加上右子节点的值。
- 计算通过当前节点的最大路径和，即左子节点的最大单边路径和加上当前节点的值再加上右子节点的最大单边路径和，与全局最大路径和比较，更新全局最大路径和。
- 返回当前节点的最大单边路径和，即当前节点的值加上左右子节点单边路径和的较大者。
递归结束后，全局变量中记录的就是最大路径和。
Golang 版本
package main
import (
"fmt"
"math"
)
// TreeNode is the structure for binary tree nodes.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// maxPathSum finds the maximum path sum for any path in the binary tree.
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
var maxGain func(node *TreeNode) int
maxGain = func(node *TreeNode) int {
if node == nil {
return 0
}
// Recursively call maxGain on node's left and right subtrees
leftGain := max(0, maxGain(node.Left))
rightGain := max(0, maxGain(node.Right))
// Price to start a new path where `node` is the highest node
priceNewpath := node.Val + leftGain + rightGain
// Update maxSum if it's better to start a new path
maxSum = max(maxSum, priceNewpath)
// For recursion return the max gain if continue the same path
return node.Val + max(leftGain, rightGain)
}
maxGain(root)
return maxSum
}
// max returns the larger of x or y.
func max(x, y int) int {
if x > y {
return x
}
return y
}
func main() {
// Example usage:
// Construct a binary tree:
// 1
// / \
// 2 3
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
// Find the maximum path sum
fmt.Println("Maximum Path Sum:", maxPathSum(root))
}
这段代码定义了一个二叉树节点的结构体TreeNode，并实现了一个函数maxPathSum来计算二叉树中任意路径的最大路径和。在main函数中，我们构造了一个简单的二叉树作为示例，并调用maxPathSum函数来计算和打印最大路径和。
C++版本
#include <iostream>
#include <algorithm>
#include <climits>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
maxPathDown(root, maxSum);
return maxSum;
}
private:
int maxPathDown(TreeNode* node, int& maxSum) {
if (node == nullptr) return 0;
int left = std::max(0, maxPathDown(node->left, maxSum));
int right = std::max(0, maxPathDown(node->right, maxSum));
maxSum = std::max(maxSum, left + right + node->val);
return std::max(left, right) + node->val;
}
};
int main() {
// Example usage:
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
Solution solution;
std::cout << "Maximum Path Sum: " << solution.maxPathSum(root) << std::endl;
// Clean up memory
delete root->left;
delete root->right;
delete root;
return 0;
}
这段 C++代码定义了一个二叉树节点的结构体TreeNode和一个解决方案类Solution。Solution类中有一个公共成员函数maxPathSum用来计算二叉树中任意路径的最大路径和，以及一个私有成员函数maxPathDown用来递归地计算从任意节点向下的最大路径和。在main函数中，我们构造了一个简单的二叉树作为示例，并调用maxPathSum函数来计算和打印最大路径和。最后，代码中还包含了适当的内存清理操作。
Python 版本
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.max_sum = float('-inf')
def max_gain(node):
if not node:
return 0
# Recursively call max_gain on node's left and right subtrees
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
# Price to start a new path where `node` is the highest node
price_newpath = node.val + left_gain + right_gain
# Update max_sum if it's better to start a new path
self.max_sum = max(self.max_sum, price_newpath)
# For recursion, return the max gain if continue the same path
return node.val + max(left_gain, right_gain)
max_gain(root)
return self.max_sum
# Example usage:
if __name__ == "__main__":
# Construct a binary tree:
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
# Find the maximum path sum
solution = Solution()
print("Maximum Path Sum:", solution.maxPathSum(root))
这段 Python 代码定义了一个二叉树节点的类TreeNode和一个解决方案类Solution。Solution类中有一个方法maxPathSum用来计算二叉树中任意路径的最大路径和。在maxPathSum方法中，定义了一个内部函数max_gain用来递归地计算从任意节点向下的最大路径和，并更新一个类属性max_sum作为全局最大路径和。在__main__部分，我们构造了一个简单的二叉树作为示例，并调用maxPathSum方法来计算和打印最大路径和。
Java 版本
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
return node.val + Math.max(leftGain, rightGain);
}
}
public class Main {
public static void main(String[] args) {
// Example usage:
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
Solution solution = new Solution();
System.out.println("Maximum Path Sum: " + solution.maxPathSum(root));
}
}
这段 Java 代码定义了一个二叉树节点的类TreeNode和一个解决方案类Solution。Solution类中有一个方法maxPathSum用来计算二叉树中任意路径的最大路径和。在maxPathSum方法中，定义了一个私有辅助方法maxGain用来递归地计算从任意节点向下的最大路径和，并更新一个私有成员变量maxSum作为全局最大路径和。在Main类的main方法中，我们构造了一个简单的二叉树作为示例，并调用maxPathSum方法来计算和打印最大路径和。
Rust 版本
use std::cell::RefCell; use std::rc::Rc; use std::cmp; // Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } struct Solution; impl Solution { pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { let mut max_sum = i32::MIN; Solution::max_gain(root, &mut max_sum); max_sum } fn max_gain(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i32) -> i32 { match node { Some(node) => { let n = node.borrow(); let left_gain = cmp::max(Self::max_gain(n.left.clone(), max_sum), 0); let right_gain = cmp::max(Self::max_gain(n.right.clone(), max_sum), 0); let price_newpath = n.val + left_gain + right_gain; *max_sum = cmp::max(*max_sum, price_newpath); cmp::max(n.val + left_gain, n.val + right_gain) } None => 0, } } } fn main() { // Example usage: let root = Some(Rc::new(RefCell::new(TreeNode::new(1)))); let left = Some(Rc::new(RefCell::new(TreeNode::new(2)))); let right = Some(Rc::new(RefCell::new(TreeNode::new(3)))); if let Some(r) = root.as_ref() { r.borrow_mut().left = left; r.borrow_mut().right = right; } println!("Maximum Path Sum: {}", Solution::max_path_sum(root)); }
这段 Rust 代码定义了一个二叉树节点的结构体TreeNode和一个解决方案结构体Solution。Solution结构体中有一个公共关联函数max_path_sum用来计算二叉树中任意路径的最大路径和。在max_path_sum函数中，定义了一个私有关联函数max_gain用来递归地计算从任意节点向下的最大路径和，并更新一个可变引用参数max_sum作为全局最大路径和。在main函数中，我们构造了一个简单的二叉树作为示例，并调用max_path_sum函数来计算和打印最大路径和。
总结
上述解法采用了递归的方法来解决二叉树中的最大路径和问题。核心思想是对于每个节点，计算两个值：
-
节点的最大单边路径和：这是从当前节点出发，到任意子节点的最大路径和，不包括父节点。这个值是当前节点的值加上其左右子节点的最大单边路径和的较大者。如果子节点的最大单边路径和为负，则不包括该子节点，因为路径和会减小。
-
可能的最大路径和：这是以当前节点为根的子树能提供的最大路径和，可能包括左右子节点的最大单边路径和加上当前节点的值。这个值可能不会返回给父节点，但会用来更新全局的最大路径和。
算法的步骤如下：
- 从根节点开始递归。
- 对于每个节点，递归计算其左右子节点的最大单边路径和。
- 计算以当前节点为顶点的最大路径和（当前节点值 + 左侧最大单边路径和 + 右侧最大单边路径和）。
- 更新全局最大路径和（如果当前节点的最大路径和更大）。
- 返回当前节点的最大单边路径和给父节点。
这个算法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为每个节点只被访问一次。空间复杂度是 O(h)，其中 h 是树的高度，这是因为递归栈的深度取决于树的高度。
在不同的编程语言中，这个算法的实现细节可能略有不同，但核心逻辑是一致的。例如，在 Rust 中，由于其所有权模型，我们需要使用Rc<RefCell<T>>来共享和修改树节点。而在 Java 中，我们可以直接修改对象的属性。