public int maxPathSumRec(TreeNode root) {// return a path that must end up at root
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;

        int pathSumLeft = maxPathSumRec(root.left);
        int pathSumRight = maxPathSumRec(root.right);
        int maxCur = Math.max(Math.max(root.val, pathSumLeft + root.val), Math.max(pathSumRight + root.val, pathSumLeft + pathSumRight + root.val));
        res = Math.max(res, maxCur);

        return root.val + Math.max(0, Math.max(pathSumLeft, pathSumRight));
    }