124 Binary Tree Maximum Path Sum

Leetcode

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

---

使用一个 max 方法对树进行递归遍历，返回值为以此作为子路径能得到的最大值。总的最大值有多种情况，当前节点为根节点，最大值为当前节点的值加上左子树返回值和右子树返回值（如果两个都是正的），如果左右子树只有一个是正的，只加上正的，如果只有一个子树存在，最大值为当前节点的值加上子树的返回值（如果返回值为正），或当前节点的值（子树返回值为负）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        max=Integer.MIN_VALUE;
        max(root);
        return max;
    }
    
    private int max(TreeNode root){
        int total=root.val;
        if(root.left!=null && root.right!=null){
            int left=max(root.left);
            int right=max(root.right);
            if(total+left+right>max) max=total+left+right;
            int bigger=left>right?left:right;
            if(bigger<0) bigger=0;            
            total+=bigger;
        } else if(root.left!=null){
            int left=max(root.left);
            if(left<0) left=0;
            total+=left;
        } else if(root.right!=null){
            int right=max(root.right);
            if(right<0) right=0;
            total+=right;
        }
        if(total>max) max=total;
        return total;
    }
}