美文网首页
Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

作者: BLUE_fdf9 | 来源:发表于2018-08-22 23:30 被阅读0次

题目
Given a non-empty 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 connections. The path must contain at least one node and does not need to go through the root.

答案

class Solution {
    int globalMax = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        recur(root);
        return globalMax;
    }
    public int recur(TreeNode root) {
        if(root == null) return 0;
        
        // Cut negative part
        int left = Math.max(0, recur(root.left));
        int right = Math.max(0, recur(root.right));

        int localMax = left + right + root.val;
        globalMax = Math.max(globalMax, localMax);
        
        return Math.max(left, right) + root.val;
    }
}

相关文章

网友评论

      本文标题:Binary Tree Maximum Path Sum

      本文链接:https://www.haomeiwen.com/subject/bjvuiftx.html