【hard】124. Binary Tree Maximum Path Sum

清疚 2023-08-17 17:20 47阅读 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:

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

Example 2:

Input: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    Output: 42

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        int solution(TreeNode* root, int& best){  // my own solution
            if (!root) return 0;
            int left_sum = root->val + solution(root->left, best);
            int right_sum = root->val + solution(root->right, best);
            int curve_sum = left_sum + right_sum - root->val;
            best = max({best, left_sum, right_sum, curve_sum, root->val});
            
            return max({left_sum, right_sum, root -> val});
        }
        
    public:
        int maxPathSum(TreeNode* root) {  // it is the original function
            int best = INT_MIN;
            int eval = solution(root, best);
            return max(best, eval);
        }
        
    };

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

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

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

相关阅读

相关【hard】124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is d

清疚/ 2023年08月17日 17:20/ 0 赞/ 48 阅读

相关【NewCode-LeetCode】binary-tree-maximum-path-sum

题目：[传送门][Link 1] 题意：问题就类似于在一个无向图中，以某个点为起点，以另一个点为终点，使其从起点到终点的路劲和最大，而这里就是把无向图变成了二叉树

﹏ヽ暗。殇╰゛Y/ 2023年02月22日 13:47/ 0 赞/ 24 阅读

相关 LeetCode - Hard - 124. Binary Tree Maximum Path Sum

Topic Tree Depth-first Search Recursion Description [https://leetcode.co

我不是女神ヾ/ 2022年10月14日 01:12/ 0 赞/ 22 阅读

相关 LeetCode124—Binary Tree Maximum Path Sum

LeetCode124—Binary Tree Maximum Path Sum 原题 > Given a binary tree, find the maximu

Love The Way You Lie/ 2022年08月21日 10:59/ 0 赞/ 28 阅读

相关 Binary Tree Maximum Path Sum--LeetCode

题目： Given a binary tree, find the maximum path sum. The path may start and end at an

忘是亡心i/ 2022年08月07日 12:38/ 0 赞/ 31 阅读

相关 leetcode 124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is defined as

谁践踏了优雅/ 2022年07月26日 12:23/ 0 赞/ 153 阅读

相关 leetcode 124. Binary Tree Maximum Path Sum 最大路径和 + DFS深度优先搜索

Given a binary tree, find the maximum path sum. For this problem, a path is defined as

缺乏、安全感/ 2022年06月08日 04:55/ 0 赞/ 171 阅读

相关 LeetCode-124：Binary Tree Maximum Path Sum

题目 ![70][] 很高兴leetcode上点击量最高的解法和我一样，而且这题难度也就Medium吧我真是提交了n多遍才理解了这题什么意思：在二叉树中，

迷南。/ 2022年05月15日 08:08/ 0 赞/ 132 阅读

相关【Leetcode】124. Binary Tree Maximum Path Sum（二叉树最大路径）

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is d

女爷i/ 2022年02月13日 03:53/ 0 赞/ 204 阅读

相关 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is defined as

迷南。/ 2021年12月17日 10:35/ 0 赞/ 194 阅读