题目描述

给定一棵二叉树，找出所有从根节点到叶子节点的路径。 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。

输入格式

第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n（1<= n <= 10） ， 根结点为 1。接下来有 n 行， 依次对应二叉树的 n 个结点。

输出格式

多行，一行一个路径。路径由从根到叶的结点编号组成。多个路径按先左后右顺序输出。

样例

输入样例 1

7
2 6
3 4
-1 -1
5 -1
-1 -1
-1 7
-1 -1

输出样例 1

1 2 3
1 2 4 5
1 6 7

输入样例 2

10
2 10
3 -1
4 9
5 8
6 7
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1

输出样例 2

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 8
1 2 3 9
1 10

输入样例 3

1
-1 -1

输出样例 3

1