脚本宝典收集整理的这篇文章主要介绍了

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群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过