题解 | #二叉树中的最大路径和#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
  /*难点：用re 存贮 left+right+root的场景，这个场景无法包含更早的root节点*/
    static long re = Integer.MIN_VALUE;
    
    public int F (TreeNode root){
        long left = Integer.MIN_VALUE,right = Integer.MIN_VALUE;
        long max = Integer.MIN_VALUE;
        if(root==null) return 0;
        if(root.left!=null) left = F(root.left);
        if(root.right!=null) right = F(root.right);
        
        max = root.val;
        max = Math.max(max,root.val+left);
        max = Math.max(max,root.val+right);

        re = Math.max(re,root.val);
        re = Math.max(re,right);
        re = Math.max(re,left);
        re = Math.max(re,root.val+right+left);
        return (int) max;
    }
    
    public int maxPathSum (TreeNode root) {

        int tmp = F(root);
       return  Math.max((int)re,tmp);
    }
}