题解 | #二叉树的最大路径和#

二叉树任意节点之间的最大路径和=根结点的值+左子树的最大路径+右子树的最大路径。递归求解。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int max_path{INT_MIN};
    int path_sum(TreeNode* root){
        if(root==nullptr) return 0;
        int left_path=max(0, path_sum(root->left));
        int right_path=max(0, path_sum(root->right));
        max_path=max(max_path, root->val + left_path + right_path);
        return max(root->val + left_path, root->val + right_path);
    }
    
    int maxPathSum(TreeNode* root) {
        int reuslt=path_sum(root);
        return max_path;
    }
};