路径总和 II

题目描述

给定一棵二叉树的根节点 root 和一个整数目标和 targetSum，请找出所有从根节点到叶子节点的路径，使得路径上所有节点值之和等于 targetSum。

叶子节点是指没有子节点的节点。

输入格式

第一行输入两个整数 n 和 targetSum，表示二叉树层序序列的长度以及目标和。

第二行输入 n 个字符串，表示二叉树的层序遍历结果，其中：

• 非 null 字符串表示该节点的整数值；
• null 表示该位置为空节点。

保证输入序列能够唯一确定一棵二叉树，且根节点非空。

输出格式

第一行输出一个整数 k，表示满足条件的路径数量。

接下来输出 k 行，每行先输出一个整数 len，表示该路径长度，随后输出这条路径上的所有节点值。

路径按照深度优先搜索时“先左后右”找到的顺序输出。

数据范围

1 <= n <= 5000

-1000 <= Node.val, targetSum <= 1000

样例 1

输入

13 22
5 4 8 11 null 13 4 7 2 null null 5 1

输出

2
4 5 4 11 2
4 5 8 4 5