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

素颜马尾好姑娘i 2022-12-09 13:59 142阅读 0赞

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

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

示例 1：
    
    输入：[1,2,3]
    
           1
          / \
         2   3
    
    输出：6
    示例 2：
    
    输入：[-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    输出：42
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

发表评论取消回复

表情：

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

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

相关阅读

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

一、前言标签：树\_最大路径。问题来源LeetCode 124 难度：困难。问题链接：[https://leetcode-cn.com/problems/bin

末蓝、/ 2023年03月01日 12:27/ 0 赞/ 121 阅读

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

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

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

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

题目： [124. 二叉树中的最大路径和][124.] [\[编程题\]二叉树的最大路径和][Link 1] ![在这里插入图片描述][watermark_typ

淩亂°似流年/ 2022年12月11日 12:26/ 0 赞/ 162 阅读

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

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

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

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

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

墨蓝/ 2022年10月10日 04:44/ 0 赞/ 162 阅读

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

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

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

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

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

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

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

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

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

相关【LeetCode】第124题：二叉树的最大路径和

LeetCode 链接：[https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/][https_leetc

约定不等于承诺〃/ 2021年12月12日 00:27/ 0 赞/ 214 阅读

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

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

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