【hard】124. Binary Tree Maximum Path Sum

清疚 2023-08-17 17:20 31阅读 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 条评论，31人围观）

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

相关阅读

相关【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 赞/ 32 阅读

相关 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 赞/ 3 阅读

相关 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 赞/ 136 阅读

相关 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 赞/ 152 阅读

相关二叉树的最长路径和（Binary Tree Maximum Path Sum）

题目： Given a binary tree, find the maximum path sum. For this problem, a path is defin

你的名字/ 2022年06月07日 04:19/ 0 赞/ 180 阅读

相关 654. Maximum Binary Tree

654. Maximum Binary Tree ![这里写图片描述][SouthEast] 这道题是中等难度的题目，一开始想到的解法是选择递归，因为这个问题本身就是递

深碍√TFBOYSˉ_/ 2022年06月04日 00:47/ 0 赞/ 172 阅读

相关 LeetCode刷题笔记（树）：binary-tree-maximum-path-sum

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

爱被打了一巴掌/ 2022年05月25日 13:25/ 0 赞/ 162 阅读

相关 LeetCode 124.Binary Tree Maximum Path Sum （二叉树中的最大路径和）

题目描述：给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1

古城微笑少年丶/ 2022年05月08日 05:30/ 0 赞/ 153 阅读

相关【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 赞/ 183 阅读

相关 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 赞/ 174 阅读