124. Binary Tree Maximum Path Sum

时间:2019-09-05
本文章向大家介绍124. Binary Tree Maximum Path Sum,主要包括124. Binary Tree Maximum Path Sum使用实例、应用技巧、基本知识点总结和需要注意事项,具有一定的参考价值,需要的朋友可以参考一下。

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.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

?  -10
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7

Output: 42
public class Solution {
    int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
// helper returns the max branch // plus current node's value int helper(TreeNode root) { if (root == null) return 0; //如果最大值是负值就不选 int left = Math.max(helper(root.left), 0); int right = Math.max(helper(root.right), 0); //求的时候考虑包括当前根节点的最大路径 max = Math.max(max, root.val + left + right); //返回根值和左右子树较大的值,只能选一个,不然无法实现 return root.val + Math.max(left, right); } }

可以从任何地方开始,求根+左+右的最大值。

很难

https://leetcode.wang/leetcode-124-Binary-Tree-Maximum-Path-Sum.html

$flag 上一页

上一篇:HDU-1828 Picture(扫描线 求矩形并的周长)

下一篇:已是最后一篇