二叉树最大路径和

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

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

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

提示：

• 树中节点数目范围是$[1, 3 * 10^4]$
• -1000 <= Node.val <= 1000

124.二叉树的最大路径和

其实我感觉题目有点不说人话

这题相当于，把二叉树当成一个无向图，求所经过结点之和最大的路径。

这题可以递归解，单独考虑只有根节点、左节点和右节点的二叉树。由于迭代是向上的，所以是一颗颗这样的小树组成一整颗大树。对于一颗小树，可以有如下几个选择：

• 和上端大树相连

1. 选择根节点
2. 选择根节点、左节点
3. 选择根节点、右节点

• 不和上端大树相连，重新开辟新的路径

1. 选择左节点、根节点、右节点
2. 选择左节点
3. 选择右节点

和上端大树相连的情况，可以返回三者取max的结果作为返回值；而不和上端大树相连的情况，可以单独缓存至一个变量里，每次递归时更新该值即可。

/**
 * 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 {
    int ans = -INT_MAX;
public:
    int maxPathSum(TreeNode* root) {
        int res = recur(root);
        return max(res, ans);
    }
    int recur(TreeNode* node){
        if(node == nullptr){
            return -INT_MAX / 3;
        }
        int left = recur(node->left);
        int right = recur(node->right);
        ans = max({ans, left, right, left + node->val + right});
        return max({node->val, node->val + left, node->val + right});
    }
};