专业的营销型网站制作,政务网站建设浙江,wordpress 移除 新闻,外包公司为什么没人去给定一个非空二叉树#xff0c;返回其最大路径和。
本题中#xff0c;路径被定义为一条从树中任意节点出发#xff0c;达到任意节点的序列。该路径至少包含一个节点#xff0c;且不一定经过根节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3
输出: 6 示例 2:
输…给定一个非空二叉树返回其最大路径和。
本题中路径被定义为一条从树中任意节点出发达到任意节点的序列。该路径至少包含一个节点且不一定经过根节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3
输出: 6 示例 2:
输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7
输出: 42 思路
递归
为每个点设置一个最大值表示已这个结点为中心这个点的值加上他的左右子树最大值是多少
返回的也是这个值 每次递归返回的值是这个点的值和他的max左子树值右子树值 代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */
class Solution { int max -21474836471; public int maxPathSum(TreeNode root) { if(rootnull) return 0; helper(root); return max; } public int helper(TreeNode root){ if(rootnull){ return 0; } int left Math.max(0,helper(root.left)); int right Math.max(0,helper(root.right)); int maxnum root.valleftright; max Math.max(max,maxnum); return root.valMath.max(left,right); }
}
