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

View as PDF



Author:
Problem types
Points: 1900 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

There are three common ways to traverse the nodes of a binary tree:

  • Preorder: First process the root, then the left subtree, and finally the right subtree.
  • Inorder: First process the left subtree, then the root, and finally the right subtree.
  • Postorder: First process the left subtree, then the right subtree, and finally the root.

There is a binary tree of \(n\) nodes with distinct labels. You are given the preorder and inorder traversals of the tree, and your task is to determine its postorder traversal.

Input

  • The first input line has an integer \(n\): the number of nodes. The nodes are numbered \(1,2,…,n\).
  • After this, there are two lines describing the preorder and inorder traversals of the tree. Both lines consist of \(n\) integers.
  • You can assume that the input corresponds to a binary tree.

Output

  • Print the postorder traversal of the tree.

Constraints

  • \(1 \leq n \leq 10^5\)

Example

Sample input

5  
5 3 2 1 4  
3 5 1 2 4

Sample output

3 1 4 2 5


Comments


  • 0
    nguyen_ducminh    12:32 a.m. 2 sep, 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