脚本宝典收集整理的这篇文章主要介绍了Binary Tree Maximum Path Sum@LeetCode，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Binary Tree Maximum Path Sum
动态规划+深度优先搜索。把大问题（求整棵树的路径最大值）拆分成小问题（每颗子树的路径最大值），递推公式为：当前树的路径最大值=max(左子树的路径最大值, 右子树的路径最大值)+当前根节点的值。以此来推出最后全树的最大路径值。
实现代码：
public class Solution {
private int max;
public int maxPathSum(TreeNode root) {
if (root == null)
return 0;
max = root.val;
traversal(root);
return max;
}
private int traversal(TreeNode node) {
int left = node.left == null ? 0 : traversal(node.left);
int right = node.right == null ? 0 : traversal(node.right);
left = left <= 0 ? 0 : left;
right = right <= 0 ? 0 : right;
max = Math.max(max, left + node.val + right);
node.val = node.val + Math.max(left, right);
return node.val;
}
}
以上是脚本宝典为你收集整理的Binary Tree Maximum Path Sum@LeetCode全部内容，希望文章能够帮你解决Binary Tree Maximum Path Sum@LeetCode所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。