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

import java.util.*;

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

public class Solution {

    //定义全局最小结果 临时变量 记录每一颗子树的最大路径和
    public int max = Integer.MIN_VALUE;

    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {

        if (root == null) {
            return 0;
        }

        treeDeep(root);

        return max;
    }

    //后续遍历 以每一个节点看成一颗树 计算该树的最大路径值
    public int treeDeep (TreeNode root) {

        if(root == null) {
            return 0;
        }

        //左子树如果<0 则舍弃认为该子树的最大路径和为0
        int left = Math.max(0, treeDeep(root.left));

        //右子树如果<0 则舍弃认为该子树的最大路径和为0
        int right = Math.max(0, treeDeep(root.right));

        //临时变量 记录以当前节点为根节点的,每一颗子树的最大路径和 
        //最大路径和 = 根节点 + 左孩子(左子树如果<0 则舍弃认为该子树的最大路径和为0) + 右孩子(右子树如果<0 则舍弃认为该子树的最大路径和为0)
        //即:当前子树的最大路径和只能为以下4种情况
        //1: root.val 左孩子右孩子都<0 那么以该root为根节点的子树最大路径和为root.val + 0 + 0
        //2: root.val 左孩子>0 右孩子<0 那么以该root为根节点的子树最大路径和为 root.val + left.val + 0
        //3: root.val 左孩子<0 右孩子>0 那么以该root为根节点的子树最大路径和为 root.val + right.val + 0
        //4: root.val 左孩子>0 右孩子>0 那么以该root为根节点的子树最大路径和为 root.val + left.val + right.val
        //结果就是 root.val + left.val + right.val 包含了以上4种情况 因为左右孩子的值 在上面有和0做比较 取最大的
        max = Math.max(max, root.val + left + right);

        /**
         *               1
         *         2           5
         *     3      4
         * 此时已经用max保留了 以2为根节点的子树 234的最大和尾 9
         * 但此时可能 3->2->4可能不是最大的路径和,所以此时应该保留2+4=6作为1的左孩子
         *               1
         *         2           5
         *            4
         *            变为:再进行递归计算最大路径
         *               1
         *         6           5
         */
        return root.val + Math.max(left, right);    
    }
}