题目

类型：DFS
难度：困难
image.png

解题思路

递归
maxGain(node)
该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

  • 空节点的最大贡献值等于 0。

  • 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

    代码

    1. class Solution {
    2.   int maxSum = Integer.MIN_VALUE;
    4.   public int maxPathSum(TreeNode root) {
    5.       maxGain(root);
    6.       return maxSum;
    7.   }
    9.   public int maxGain(TreeNode node) {
    10.       if (node == null) {
    11.           return 0;
    12.       }
    14.       // 递归计算左右子节点的最大贡献值
    15.       // 只有在最大贡献值大于 0 时，才会选取对应子节点
    16.       int leftGain = Math.max(maxGain(node.left), 0);
    17.       int rightGain = Math.max(maxGain(node.right), 0);
    19.       // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    20.       int priceNewpath = node.val + leftGain + rightGain;
    22.       // 更新答案
    23.       maxSum = Math.max(maxSum, priceNewpath);
    25.       // 返回节点的最大贡献值
    26.       return node.val + Math.max(leftGain, rightGain);
    27.   }
    28. }