题目内容

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

叶子节点是指没有左子节点和右子节点的节点。

对于每一条满足条件的路径，需要按照从根节点到叶子节点的顺序输出路径上的所有节点值。

如果存在多条满足条件的路径，则按照从左到右的深度优先遍历顺序输出。

输入描述

第一行输入两个整数 $n$ 和 $targetSum$，其中 $n$ 表示二叉树层序序列中的元素个数，$targetSum$ 表示目标路径和。

第二行输入 $n$ 个元素，表示二叉树的层序遍历序列。

其中，非空节点使用整数表示，空节点使用字符串 $null$ 表示。

若 $n=0$，则表示二叉树为空，此时第二行可以省略。

约束

二叉树中非空节点的个数不超过 $5000$。

$-1000 \le Node.val \le 1000$

$-1000 \le targetSum \le 1000$

输出描述

第一行输出一个整数 $k$，表示满足条件的根节点到叶子节点路径数量。

接下来输出 $k$ 行，每行表示一条满足条件的路径，按照从根节点到叶子节点的顺序输出路径中的所有节点值，相邻整数之间用空格分隔。

如果不存在满足条件的路径，则只输出一行 $0$。

样例1

输入

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

输出

2
5 4 11 2
5 8 4 5

说明

第一条满足条件的根节点到叶子节点路径为 $5,4,11,2$，路径和为

$5+4+11+2=22$

第二条满足条件的路径为 $5,8,4,5$，路径和为

$5+8+4+5=22$

因此共有 $2$ 条满足条件的路径。

样例2

输入

3 5
1 2 3

输出

0

说明

从根节点到左叶子节点的路径和为

$1+2=3$

从根节点到右叶子节点的路径和为

$1+3=4$

均不等于 $targetSum=5$，因此不存在满足条件的路径。

样例3

输入

2 0
1 2

输出

0

说明

二叉树中唯一的根节点到叶子节点路径为 $1,2$，路径和为

$1+2=3$

不等于 $targetSum=0$，因此不存在满足条件的路径。