135 lines
4.0 KiB
Markdown
135 lines
4.0 KiB
Markdown
Q1
|
||
```
|
||
编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。
|
||
|
||
输入格式:
|
||
输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示要进行的删除操作次数。接下来m行，每行一个不等于0的整数K，表示要删除以K为根的子树。m不超过100，二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等，且删除子树后二叉树不为空。
|
||
|
||
PA567.jpg
|
||
|
||
输出格式:
|
||
输出为m行，每行为一组整数，表示执行删除操作后剩余二叉树的中根序列（中根序列中每个整数后一个空格）。若要删除的子树不在当前二叉树中，则该行输出0（0后无空格）。
|
||
|
||
输入样例:
|
||
1 5 8 0 0 0 6 0 0
|
||
3
|
||
5
|
||
8
|
||
6
|
||
输出样例:
|
||
1 6
|
||
0
|
||
1
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
100 ms
|
||
内存限制
|
||
10 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q2
|
||
```
|
||
已知二叉树结点为不等于0的整数。给定一个整数K，请编写程序找出以根结点为起点叶结点为终点的所有路径中，结点值之和等于K的所有路径。例如K=15，对于下图所示的二叉树t，满足条件的路径有2条，即8-5-2和8-7。若没有满足条件的路径，则亦能识别。
|
||
|
||
img.jpg
|
||
|
||
输入格式:
|
||
输入为2行，第一行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。第2行为整数K。
|
||
|
||
输出格式:
|
||
输出第一行为一个整数，表示满足条件的路径条数；若没有满足条件的路径，则输出0。从第二行开始，每行为一条满足条件的路径，若有多条满足条件的路径，则按从左到右的顺序依次输出，路径中每个结点值后一个空格，若两条不同的路径包含的各结点值恰好相等，则都需输出。
|
||
|
||
输入样例1:
|
||
8 5 1 0 0 2 0 0 7 0 0
|
||
15
|
||
输出样例1:
|
||
2
|
||
8 5 2
|
||
8 7
|
||
输入样例2:
|
||
-1 2 0 0 3 0 0
|
||
2
|
||
输出样例2:
|
||
1
|
||
-1 3
|
||
输入样例3:
|
||
1 1 0 0 1 0 0
|
||
2
|
||
输出样例3:
|
||
2
|
||
1 1
|
||
1 1
|
||
输入样例4:
|
||
-1 2 0 0 3 0 0
|
||
8
|
||
输出样例4:
|
||
0
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q3
|
||
```
|
||
给定一棵非空二叉树，结点数据域值为互不相等且不等于0的正整数，同时给定两个正整数a和b，请编写程序输出数据域值为a和b的两个结点间的路径和路径长度。注意本题的路径不受父子关系约束，只要两个结点间有边，就算路径。例如下图所示二叉树，7和8间的路径为7 5 8，路径长度为2；6和8间的路径为6 3 5 8，路径长度为3；9和8间的路径为9 2 1 3 5 8，路径长度为5。9和1之间的路径为9 2 1，路径长度为2。
|
||
|
||
223.jpg
|
||
|
||
输入格式:
|
||
输入第一行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，二叉树结点个数不超过150000，高度不超过5000。第二行为一个整数T，表示查询数目。接下来T行，每行两个互不相等的正整数a和b，含义如题目所述，保证a和b一定在二叉树中。
|
||
|
||
输出格式:
|
||
对于每个查询输出为两行整数。第一行为1个整数，表示两个结点间的路径长度，第二行为1行整数，每个整数后一个空格，表示路径。
|
||
|
||
输入样例1:
|
||
1 2 9 0 0 0 3 5 7 0 0 8 0 0 6 0 0
|
||
3
|
||
7 8
|
||
6 8
|
||
9 8
|
||
输出样例1:
|
||
2
|
||
7 5 8
|
||
3
|
||
6 3 5 8
|
||
5
|
||
9 2 1 3 5 8
|
||
输入样例2:
|
||
1 2 0 4 0 7 0 0 3 5 0 0 6 8 20 0 0 21 0 0 0
|
||
3
|
||
7 8
|
||
5 8
|
||
20 21
|
||
输出样例2:
|
||
6
|
||
7 4 2 1 3 6 8
|
||
3
|
||
5 3 6 8
|
||
2
|
||
20 8 21
|
||
输入样例3:
|
||
2 4 3 0 0 8 0 0 10 5 7 9 0 0 1 0 0 17 0 0 6 0 0
|
||
3
|
||
8 3
|
||
9 17
|
||
1 6
|
||
输出样例3:
|
||
2
|
||
8 4 3
|
||
3
|
||
9 7 5 17
|
||
4
|
||
1 7 5 10 6
|
||
数据规模:
|
||
测试点0-2、5-9：结点个数≤50，树高≤20
|
||
测试点3：4500≤结点个数≤5500，4000≤树高≤5000
|
||
测试点4：130000≤结点个数≤150000，10≤树高≤20
|
||
``` |