Hard

题目描述

二叉树中的路径被定义为一条从树中任意节点出发，沿父子连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

  • 树中节点数目范围是 [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000

解题思路

这道题的关键在于理解路径的定义：路径可以从任意节点开始，到任意节点结束，不一定经过根节点。我们需要考虑所有可能的路径组合。

核心思路：

使用递归的深度优先搜索，对于每个节点，考虑以该节点为"拐点"的最大路径和。一条经过节点的路径可以分为三部分：左子树路径 + 当前节点 + 右子树路径。

递归函数设计：

设计递归函数 maxGain(node)，返回以该节点为起点的单边最大路径和（只能向左或向右，不能同时向两边）。这样设计是因为如果一个节点要作为其父节点路径的一部分，它只能贡献单边路径。

状态更新：

在每个节点处，计算经过该节点的最大路径和：left_gain + node.val + right_gain，并更新全局最大值。但要注意，负的贡献应该被忽略（取0）。

边界处理：

空节点返回0。对于叶子节点，其最大贡献就是节点值本身（如果为正）或0（如果为负）。

这种方法确保了每个可能的路径都被考虑到，时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。

代码实现

class Solution {
private:
    int maxSum;
    
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        
        int currentMax = node->val + leftGain + rightGain;
        maxSum = max(maxSum, currentMax);
        
        return node->val + max(leftGain, rightGain);
    }
    
public:
    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        maxGain(root);
        return maxSum;
    }
};

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            current_max = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_max)
            
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum

public class Solution {
    private int maxSum;
    
    public int MaxPathSum(TreeNode root) {
        maxSum = int.MinValue;
        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 currentMax = node.val + leftGain + rightGain;
        maxSum = Math.Max(maxSum, currentMax);
        
        return node.val + Math.Max(leftGain, rightGain);
    }
}

var maxPathSum = function(root) {
    let maxSum = -Infinity;
    
    function maxGain(node) {
        if (!node) return 0;
        
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        const currentMax = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentMax);
        
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次，其中 n 是节点数
空间复杂度O(h)递归调用栈的深度，其中 h 是树的高度，最坏情况下为 O(n)

相关题目