• 困难
  • 中等
  • 简单

    题目描述

    给定一个非空二叉树，返回其最大路径和。

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

返回滑动窗口中的最大值。

来源，leetcode 每日一题 124. 二叉树中的最大路径和

示例：

  1. 输入：[1,2,3]
  3.        1
  4.       / \
  5.      2   3
  7. 输出：6
  9. 输入：[-10,9,20,null,null,15,7]
  11.    -10
  12.    / \
  13.   9  20
  14.     /  \
  15.    15   7
  17. 输出：42

解题思路

  1. 动态规划，将问题分解成左子树最大路径和右子树最大路径，同时比较左子树最大路径和右子树最大路径+val的结果。

    代码

    ```cpp /**
    • 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 { private: int maxSum = INT_MIN;

public: int maxGain(TreeNode* node) { if (node == nullptr) { return 0; }

    // 递归计算左右子节点的最大贡献值
    // 只有在最大贡献值大于 0 时，才会选取对应子节点
    int leftGain = max(maxGain(node->left), 0);
    int rightGain = max(maxGain(node->right), 0);

    // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    int priceNewpath = node->val + leftGain + rightGain;

    // 更新答案
    maxSum = max(maxSum, priceNewpath);

    // 返回节点的最大贡献值
    return node->val + max(leftGain, rightGain);
}

int maxPathSum(TreeNode* root) {
    maxGain(root);
    return maxSum;
}

}; // [1,2,3] // [-10,9,20,null,null,15,7] // [10,29,30,-1,-10,-192,212,21,2,3,1,23] // [-3] // [-1,5,null,4,null,null,2,-4] ```