【leetcode】No.124：binary-tree-max

题目描述

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

思路

二叉树路径最大值来源于左子树或右子树中较大的一个，思想和求数的高度差不多，需要一个变量maxValue来存全局最大值，注意可能会存在负值，需要用Math.max()函数过滤以下，负值取0就行。

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int maxValue;
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPath(root);
        return maxValue;
    }

    private int maxPath(TreeNode node){
        if (node == null)
            return 0;
        int left = Math.max(0, maxPath(node.left));
        int right = Math.max(0, maxPath(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}