首页 > 代码库 > LeetCode Binary Tree Maximum Path Sum
LeetCode Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1 / 2 3
Return 6.
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 int max = Integer.MIN_VALUE;12 public int maxPathSum(TreeNode root) {13 if (root == null) {14 return 0;15 }16 maxSum(root);17 return max;18 }19 20 private int maxSum(TreeNode root) {21 if (root == null) {22 return 0;23 }24 int leftSum=0;25 int rightSum=0;26 int val=root.val;27 if (root.left != null) {28 leftSum = maxSum(root.left);29 if (leftSum > 0) {30 val = val + leftSum;31 }32 }33 34 if (root.right != null) {35 rightSum = maxSum(root.right);36 if (rightSum > 0) {37 val = val + rightSum;38 }39 }40 41 if (val > max) {42 max = val;43 }44 45 return Math.max(root.val, Math.max(root.val + leftSum, root.val + rightSum));46 47 48 }49 }
LeetCode Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。