CSES - Tree Traversals | Thứ tự duyệt cây
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có ba cách phổ biến để duyệt qua các nút của cây nhị phân:
- Duyệt tiền tự: đầu tiên xử lý gốc, sau đó đến cây con bên trái và cuối cùng là cây con bên phải.
- Duyệt trung tự: đầu tiên xử lý cây con bên trái, sau đó đến gốc và cuối cùng là cây con bên phải.
- Duyệt hậu tự: đầu tiên xử lý cây con bên trái, sau đó đến cây con bên phải và cuối cùng là gốc.
Cho một cây nhị phân gồm \(n\) nút với các nhãn khác nhau. Bạn được cung cấp đường đi theo cách duyệt tiền tự và duyệt trung tự. Nhiệm vụ của bạn là tìm ra đường đi theo cách duyệt hậu tự.
Input
- Dòng đầu tiên gồm số nguyên \(n\): số lượng các nút. Các nút được đánh số \(1, 2,..., n\).
- Hai dòng tiếp theo mô tả đường đi theo cách duyệt tiền tự và duyệt trung tự trên cây. Cả hai dòng bao gồm \(n\) số nguyên.
- Giả định rằng đầu vào tương ứng với một cây nhị phân.
Output
- In ra đường đi theo cách duyệt hậu tự trên cây.
Constraints
- \(1 \le n \le 10^5\)
Sample Input
5
5 3 2 1 4
3 5 1 2 4
Sample Output
3 1 4 2 5
Bình luận
CSES - Tree Traversals | Duyệt cây
Có ba cách phổ biến để duyệt qua các đỉnh của một cây nhị phân:
Có một cây nhị phân gồm \(n\) đỉnh với chỉ số phân biệt. Bạn được cho thứ tự duyệt tiền tự và duyệt trung tự của cây, nhiệm vụ của bạn là xác định thứ tự duyệt hậu tự của cây.
Input
Dữ liệu đầu vào đảm bảo ứng với một cây nhị phân.
Output
Test 1
Input
Output