【hard】124. Binary Tree Maximum Path Sum

清疚 2023-08-17 17:20 145阅读 0赞

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

  1. Input: [1,2,3]
  2. 1
  3. / \
  4. 2 3
  5. Output: 6

Example 2:

  1. Input: [-10,9,20,null,null,15,7]
  2. -10
  3. / \
  4. 9 20
  5. / \
  6. 15 7
  7. Output: 42
  8. /**
  9. * Definition for a binary tree node.
  10. * struct TreeNode {
  11. * int val;
  12. * TreeNode *left;
  13. * TreeNode *right;
  14. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  15. * };
  16. */
  17. class Solution {
  18. private:
  19. int solution(TreeNode* root, int& best){ // my own solution
  20. if (!root) return 0;
  21. int left_sum = root->val + solution(root->left, best);
  22. int right_sum = root->val + solution(root->right, best);
  23. int curve_sum = left_sum + right_sum - root->val;
  24. best = max({best, left_sum, right_sum, curve_sum, root->val});
  25. return max({left_sum, right_sum, root -> val});
  26. }
  27. public:
  28. int maxPathSum(TreeNode* root) { // it is the original function
  29. int best = INT_MIN;
  30. int eval = solution(root, best);
  31. return max(best, eval);
  32. }
  33. };

转载于:https://www.cnblogs.com/sherry-yang/p/11421704.html

发表评论

表情:
评论列表 (有 0 条评论,145人围观)

还没有评论,来说两句吧...

相关阅读