Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ibrahim Mesecan.
Number of Nodes removed
You have a binary tree and you have to remove some
nodes from the tree. You want to see the number of nodes
removed:
- number of leaves removed,
- number of nodes which had one child
- number of nodes which had two children
Question:
Write a program that reads the information for a BST
and then, reads the nodes to be removed from
the tree. Then the program shows the number
of nodes removed according to
the number of children they have.
Input specification:
You will be given two integers in the beginning,
the number of nodes (n) to be added to the BST
and the number of nodes to be removed from
the tree (m). The following line will have n integers
and the last line will have m integers
where 0 ≤ m ≤ n ≤ 10,000 .
Note: Assume that the BST is
initially empty.
Output specification:
Show three integers.
Sample Input
10 5
15 8 10 8 18 2 2 9 11 9
8 3 8 11 9
|
Sample Output
1 0 2
|
Explanation:
There are 10 items given. However, Figure A shows
the tree after inserting the given nodes.
There are five nodes to be removed from the
tree. The first number is 8. And, it has two children.
Figure B shows the configuration after the removal of 8.
There is no 3 or 8 in the tree, so they do not change
the tree. Then, 11 is removed from the tree and it has
no child. And finally, 9 is given. After the removal of 8,
9 has moved up and now it has two children either.
Thus, there is 1 leaf removed. And, two nodes (8 and 9)
with two children.
Для отправки решений необходимо выполнить вход.
|