题干

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
注意：节点不可重复使用

原题链接：二叉树中最大路径和

解法示例

    // 最大路径全局变量
    private int maxPath = Integer.MIN_VALUE;

    // 解法实际调用入口
    public int maxPathSum(TreeNode root) {
        maxValue(root);
        return maxPath;
    }

    // 递归方法入口
    public int maxValue(TreeNode node) {
        // node为null，为递归终止条件，返回0值
        if (node == null) {
            return 0;
        }

        // 计算左右子树的最大路径值，开始递归
        int leftMaxValue = maxValue(node.left);
        int rightMaxValue = maxValue(node.right);
        // 如果左或右子数路径和小于0，则不走该子树，对应的路径和取为0
        leftMaxValue = Math.max(leftMaxValue, 0);
        rightMaxValue = Math.max(rightMaxValue, 0);

        // 该节点的最大路径和，为该节点值加上左右子树的值
        int maxVal = node.val + leftMaxValue + rightMaxValue;
        // 更新全局最大值
        maxPath = Math.max(maxPath, maxVal);

        // 返回该节点可供达到的两种路径中的最大值
        return node.val + Math.max(leftMaxValue, rightMaxValue);
    }