golang 解法, 执行用时: 16 ms, 内存消耗: 6.9 MB, 提交时间: 2023-04-22 12:31:05

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
    ans := math.MinInt
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0 // 没有节点，和为 0
        }
        lVal := dfs(node.Left)  // 左子树最大链和
        rVal := dfs(node.Right) // 右子树最大链和
        ans = max(ans, lVal+rVal+node.Val) // 两条链拼成路径
        return max(max(lVal, rVal)+node.Val, 0) // 当前子树最大链和
    }
    dfs(root)
    return ans
}

func max(a, b int) int { if a < b { return b }; return a }

cpp 解法, 执行用时: 24 ms, 内存消耗: 27.8 MB, 提交时间: 2023-04-22 12:30:49

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int ans = INT_MIN;
        function<int(TreeNode*)> dfs = [&](TreeNode *node) -> int {
            if (node == nullptr)
                return 0; // 没有节点，和为 0
            int l_val = dfs(node->left); // 左子树最大链和
            int r_val = dfs(node->right); // 右子树最大链和
            ans = max(ans, l_val + r_val + node->val); // 两条链拼成路径
            return max(max(l_val, r_val) + node->val, 0); // 当前子树最大链和
        };
        dfs(root);
        return ans;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 43 MB, 提交时间: 2023-04-22 12:30:36

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null)
            return 0; // 没有节点，和为 0
        int lVal = dfs(node.left); // 左子树最大链和
        int rVal = dfs(node.right); // 右子树最大链和
        ans = Math.max(ans, lVal + rVal + node.val); // 两条链拼成路径
        return Math.max(Math.max(lVal, rVal) + node.val, 0); // 当前子树最大链和
    }
}

python3 解法, 执行用时: 72 ms, 内存消耗: 23.3 MB, 提交时间: 2023-04-22 12:30:23

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        ans = -inf
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0  # 没有节点，和为 0
            l_val = dfs(node.left)  # 左子树最大链和
            r_val = dfs(node.right)  # 右子树最大链和
            nonlocal ans
            ans = max(ans, l_val + r_val + node.val)  # 两条链拼成路径
            return max(max(l_val, r_val) + node.val, 0)  # 当前子树最大链和
        dfs(root)
        return ans

python3 解法, 执行用时: 72 ms, 内存消耗: 23.5 MB, 提交时间: 2023-04-22 12:29:51

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxSum = float("-inf")

    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(node):
            if not node:
                return 0

            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)
            
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain
            
            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)
        
            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)
   
        maxGain(root)
        return self.maxSum