binary-tree-maximum-path-sum leetcode C++

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

Return6.

C++

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

    int maxDis;

public:

    int maxPathSum(TreeNode *root) {

        if(!root){

            maxDis=0;

            return -1e8;

        }

        int leftMax=maxPathSum(root->left);

        int l=max(0,maxDis);

        int rightMax=maxPathSum(root->right);

        int r=max(0,maxDis);

        maxDis=max(l,r)+root->val;

        return max(leftMax,max(rightMax,l+r+root->val));

    }

};

巴特西

binary-tree-maximum-path-sum leetcode C++

最新文章

热门文章