【Check 58】2024-04-22 - 124. 二叉树中的最大路径和

[larscheng]

124. 二叉树中的最大路径和

[larscheng]

思路

• 递归计算每个节点的最大贡献值，根节点的最大贡献值=root.val+Max(left,right)
• 递归过程中记录最大的路径和

  代码

class Solution { //递归计算每个节点的最大贡献值，根节点的最大贡献值=root.val+Max(left,right) //递归过程中记录最大的路径和 //O(n)/O(n) int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return res; }

private int maxGain(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftValue = Math.max(maxGain(root.left), 0);
    int rightValue = Math.max(maxGain(root.right), 0);

    int totalValue = root.val + leftValue + rightValue;
    res = Math.max(totalValue, res);

    return root.val + Math.max(leftValue, rightValue);
}

}

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)