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

import java.util.*;

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

public class Solution {

    private int max;
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        // write code here
        max = Integer.MIN_VALUE;
        maxPathDown(root);
        return max;
    }

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