CSES - Tree Traversals | Thứ tự duyệt cây

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Đ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


  • 0
    nguyen_ducminh    12:32 a.m. 2 Tháng 9, 2023

    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:

    • Duyệt tiền tự: Đầu tiên duyệt gốc, sau đó đến cây con trái, và cuối cùng đến cây con phải.
    • Duyệt trung tự: Đầu tiên duyệt cây con trái, sau đó đến gốc, và cuối cùng đến cây con phải.
    • Duyệt hậu tự: Đầu tiên duyệt cây con trái, sau đó đến cây con phải, và cuối cùng đến gốc.

    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òng đầu tiên gồm số nguyên \(n\) (\(1 \leq n \leq 10^5\)) - số lượng đỉnh. Các đỉnh được đánh chỉ số \(1, 2, ..., n\).
    • Hai dòng tiếp theo mô tả thứ tự duyệt tiền tự và duyệt trung tự của cây. Mỗi dòng gồm \(n\) số nguyên.

    Dữ liệu đầu vào đảm bảo ứng với một cây nhị phân.

    Output

    • In ra thứ tự duyệt hậu tự của cây.

    Test 1

    Input 
    5
5 3 2 1 4
3 5 1 2 4
    Output 
    3 1 4 2 5