脚本宝典收集整理的这篇文章主要介绍了LeetCode[124] Binary Tree Maximum Path Sum，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Leetcode[124] Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some
starting node to any node in the tree along the parent-child
The path must contain at least one node and does not need
go through the root.
For example: Given the below binary tree,
1
/
2 3
Return 6.
DFS
复杂度
O(N)
思路
对于每一节点，考虑到这一个节点为止，所能形成的最大值。Math.max(left.val, right.val) + root.val，是经过这个节点为止的能形成的最大值的一条支路。
代码
int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
int left = Math.max(0, maxPathSum(root.left));
int right = Math.max(0, maxPathSum(root.right));
sum = Math.max(sum, left + right + root.val);
return Math.max(left, right) + root.val;
}以上是脚本宝典为你收集整理的LeetCode[124] Binary Tree Maximum Path Sum全部内容，希望文章能够帮你解决LeetCode[124] Binary Tree Maximum Path Sum所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。