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,

1 / \ 2 3

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)); } };

 

转载于:https://www.cnblogs.com/vercont/p/10210291.html