编程题：二叉树路径和II

编写程序找出非空二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”定义为二叉树中的结点序列$$v_{i},...,v_{j}$$，序列中前一个结点是后一个结点的父结点，但路径不一定是以根结点为起点，也不一定是以叶结点为终点。路径的和定义为该路径所包含的所有结点的数据值之和。

### 输入格式:

输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。

### 输出格式:

输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，表示该最大路径包含的结点值（按所在层数递增顺序输出）。如果存在多条满足条件的路径，则输出最短（包含结点个数最少）者，如果存在多条最短的路径，则输出最靠左上者。

### 输入样例1:

in
1 2 0 0 3 0 0



### 输出样例1:

out
4
1 3



### 输入样例2:

in
-1 2 0 0 3 4 0 0 0



### 输出样例2:

out
7
3 4



### 输入样例3:

in
3 2 0 0 -1 4 0 0 0



### 输出样例3:

out
6
3 -1 4








答案：若无答案欢迎评论