这道题估计难在审题上,题目描述太简单了,导致提交各种情况没想到,整个代码比较简单,可以解释题目,采用递归后续遍历的方式,从叶子节点开始算起,每次计算产生两个值,一个是最大通路值(maxPathSum ),一个是子树能为父节点提供的最大单支值(findSingleBranchMaxPathSum递归返回的值)
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private Integer maxPathSum = null; public int maxPathSum(TreeNode root){ findSingleBranchMaxPathSum(root); return maxPathSum; } private int findSingleBranchMaxPathSum(TreeNode root) { int leftMaxPathSum=0; int rightMaxPathSum=0; if(root.left != null){ leftMaxPathSum = findSingleBranchMaxPathSum(root.left); } if(root.right != null){ rightMaxPathSum = findSingleBranchMaxPathSum(root.right); } int left = leftMaxPathSum<0?0:leftMaxPathSum; int right = rightMaxPathSum<0?0:rightMaxPathSum; if(maxPathSum == null){ maxPathSum = root.val+left+right; }else if(root.val+left+right>maxPathSum){ maxPathSum = root.val+left+right; } int single = left>right?left:right; return root.val+single; } }
相关推荐
LeetCode题解 - Java语言实现-181页.pdf
java面试 java面试_leetcode面试题解之最大数_java题解
LeetCode 刷题笔记 with Java 51-100(暗黑版).pdf
public void helper(TreeNode root, int level){// 当前层没有 list,新建// 取得当前层的 list迭代pub
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
java笔试题-LeetCode 刷题笔记 with Java 1-50(暗黑版)
leetcode 不会LeetCode_628--三数的最大积 给定一个整数数组,找出乘积最大的三个数,并输出最大的乘积。 示例 1: 输入:[1,2,3] 输出:6 示例 2: 输入:[1,2,3,4] 输出:24 笔记: 给定数组的长度在 [3,104] 范围...
LeetCode 刷题笔记 with Java 1-50(暗黑版).pdf
leetcode167 LeetCode167_Two-Sum-II 给定一个目标target,再数组中找到两个数,使其和为target,并返回对应数组中索引(从1开始)
leetcode题库所有数据库问题 Leetcode 所有数据库问题:Leetcode 问题 Active-Businesses-LeetCode.png 活跃用户-LeetCode.png 活动-参与者-LeetCode.png 至少合作过三次的演员和导演-LeetCode.png Ads-Performance-...
leetcode 不会LeetCode_563--二叉树倾斜 给定一棵二叉树,返回整棵树的倾斜度。 树节点的倾斜度定义为所有左子树节点值的总和与所有右子树节点值的总和之间的绝对差。 空节点的倾斜度为 0。 整棵树的倾斜度定义为...
Leetcode-Java- 一.(Sort类): 350. Intersection of Two Arrays II a.首先用HashMap遍历一遍数组nums1,Key值储存数组元素,Value(初始值为1)值储存重复元素出现次数,每出现一次加1; b.用List储存nums2中与nums...
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode ...
leetcode 答案LeetCode-答案-Java 我的 leetcode 用伪代码和分析用 java 回答
leetcode添加元素使和等于 算法思想 双指针 双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。 有序数组的 Two Sum Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 题目...
解压Leetcode-Solution-With-Java 用 Java 8 解决 Leetcode 问题 编号 问题 解决方案 困难 01 简单的 02 中等的 03 无重复字符的最长子串 中等的 04 两个有序数组的中位数 难的 653 二和 IV - 输入是 BST 简单的 ...
leetcode 树节点二叉树最大路径和 执行 : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val ...
leetcode 分类 Algorithm-Practice-EveryWeek Algorithm-Practice-EveryWeek-算法更新每周 详细记录见 算法练习记录-天 目录 刷题时建议按类型刷题,参考刷题类型分类 同时已经这样在刷题的参考 2019Year 2019-07-06...
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode ...
leetcode 2 和 c LeetCode_633--平方和 给定一个非负整数 c,你的任务是确定是否有两个整数 a 和 b 使得 a2 + b2 = c。 示例 1: 输入:5 输出:真 解释:1 * 1 + 2 * 2 = 5 示例 2: 输入:3 输出:假