【困难】124. 二叉树中的最大路径和

a binary tree node

/**
 * 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) {}
 * };
 */

二叉树的链接存储表示

二叉链表的节点结构

typedef struct btnode{
  T Element;
  struct btnode* Lchild,*Rchild;
}BTNode

二叉树结构

typedef struct btree{
  T Element;
  struct btnode* Root;
}BTree

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

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

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

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

/**
 * 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) {

    }
};

递归

/**
 * 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;//全局变量 maxSum 存储最大路径和

public:
    int maxGain(TreeNode* node) {//该函数计算二叉树中的一个节点的最大贡献值
      //在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
        if (node == nullptr) {
            return 0;//空节点的最大贡献值等于 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);//在递归过程中更新 maxSum 的值，

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);//非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);//对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。
        return maxSum;//最后得到的 maxSum 的值即为二叉树中的最大路径和
    }
};