BINTREE - Duyệt cây nhị phân
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cây nhị phân là cây mà mỗi nút có tối đa 2 con, thường được gọi là con trái và con phải. 3 phép duyệt cây nhị phân thông thường là tiền thứ tự (preorder), trung thứ tự (inorder) và hậu thứ tự (postorder):
- Duyệt tiền thứ tự cây gốc A: thăm gốc A, thăm cây con trái của A, thăm cây con phải của A.
- Duyệt trung thứ tự cây gốc A: thăm cây con trái của A, thăm gốc A, thăm cây con phải của A.
- Duyệt hậu thứ tự cây gốc A: thăm cây con trái của A, thăm cây con phải của A, thăm gốc A.
Cho danh sách duyệt tiền thứ tự và trung thứ tự của 1 cây nhị phân N đỉnh, các đỉnh được đánh số từ 1 đến N.
Yêu cầu hãy xây dựng lại cây và in ra danh sách duyệt hậu thứ tự.
Input
Dòng đầu ghi số N là số đỉnh (N <= 50 000, 40% số test N <= 1000).
Dòng thứ hai ghi N số là danh sách duyệt preorder.
Dòng thứ ba ghi N số là danh sách duyệt inorder.
Output
In ra N số là danh sách duyệt postorder của cây.
Example
Input: 6 1 5 3 4 6 2 5 1 4 6 3 2 Output: 5 6 4 2 3 1
- Người up: beo_chay_so