124. Binary Tree Maximum Path Sum

2019-09-06

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