首页 > itarticle > [leetcode] problem 124 – binary tree maximum path sum

[leetcode] problem 124 – binary tree maximum path sum

admin 11月 13, 2020 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.

Example

No.1

Input: [1,2,3]

1
2
3
 
  1
 / 
2   3

Output: 6

No.2

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

1
2
3
4
5
 
 -10
 / 
9  20
  /  
 15   7

Output: 42

Code

1
2
3
4
5
6
 
public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxPathSumHelper(root);
    return max;
}

private int maxPathSumHelper(TreeNode root) {
    if (root == null)
        return 0;

    int left = Math.max(maxPathSumHelper(root.left), 0);
    int right = Math.max(maxPathSumHelper(root.right), 0);
    max = Math.max(max, root.val + left + right);

    return Math.max(left, right) + root.val;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能