leetcode124. 二叉树中的最大路径和

淡淡的烟草味﹌ 2023-07-06 11:39 9阅读 0赞

难度困难314

给定一个**非空**二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径**至少包含一个**节点，且不一定经过根节点。

**示例 1:**

输入: [1,2,3]
    
           1
          / \
         2   3
    
    输出: 6

**示例 2:**

输入: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    输出: 42

思路：

[解释链接][Link 1]

我简化代码，全局答案最大值有一个变量记录，递归函数返回一条路最大和即可

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int max_sum = Integer.MIN_VALUE;
        public int max_gain(TreeNode node) {
            if (node == null) return 0;
            int left = Math.max(max_gain(node.left), 0);
            int right = Math.max(max_gain(node.right), 0);
            max_sum = Math.max(max_sum, node.val + left + right);
            return node.val + Math.max(left, right);
        }
    
        public int maxPathSum(TreeNode root) {
            max_gain(root);
            return max_sum;
        }
    }

[Link 1]: https://blog.csdn.net/hebtu666/article/details/84254502

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 124：二叉树中的最大路径和(python)

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

待我称王封你为后i/ 2023年10月11日 09:53/ 0 赞/ 16 阅读

相关 LeetCode_二叉树_困难_124. 二叉树中的最大路径和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一

港控/mmm°/ 2023年10月06日 22:43/ 0 赞/ 17 阅读

相关 leetcode124. 二叉树中的最大路径和

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

淡淡的烟草味﹌/ 2023年07月06日 11:39/ 0 赞/ 10 阅读

相关 leetcode 124二叉树的最大路径和

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

￡神魔★判官ぃ/ 2023年06月18日 05:56/ 0 赞/ 12 阅读

相关（js）leetcode 124. 二叉树中的最大路径和

题目： > 路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 > > 路径和是路径中各

红太狼/ 2023年01月08日 04:23/ 0 赞/ 186 阅读

相关 LeetCode 124. 二叉树中的最大路径和 JAVA

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

素颜马尾好姑娘i/ 2022年12月09日 13:59/ 0 赞/ 150 阅读

相关 Leetcode 124. 二叉树中的最大路径和

题目重述路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定

女爷i/ 2022年09月10日 00:23/ 0 赞/ 162 阅读

相关 leetcode:124. 二叉树中的最大路径和

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

超、凢脫俗/ 2022年03月16日 02:48/ 0 赞/ 212 阅读

相关 leetcode 124. 二叉树中的最大路径和

递归递归函数计算每一个结点向下延伸（可能是左或者右）的最大和路径，作为每次递归的返回值用一个全局的 maxret 记录最后的答案，递归达到叶子返回的时候不断跟新max

桃扇骨/ 2022年02月15日 04:13/ 0 赞/ 193 阅读

相关 leetcode:124. 二叉树中的最大路径和(树)

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

╰半橙微兮°/ 2021年09月28日 12:58/ 0 赞/ 228 阅读