PAT甲级——A1020 Tree Traversals

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

已知后序遍历和中序遍历输出层序遍历

 #include <iostream>

 #include <queue>

 using namespace std;

 int *pos, *ord;//存放后序和中序遍历数据

 struct Node

 {

     int val;

     Node *l, *r;

     Node(int a = ) :val(a), l(nullptr), r(nullptr) {}

 };

 Node*  createTree(int posL,int posR, int ordL, int ordR)

 {

     if (posL > posR)

         return nullptr;

     Node *root = new Node();

     root->val = pos[posR];//根节点值

     int k;

     for (k = ordL; k <= ordR; ++k)

     {

         if (ord[k] == pos[posR])//找到原树的根

             break;

     }

     int numL = k - ordL;//左子树节点数量

     //递归构造左子树

     root->l = createTree(posL, posL + numL - , ordL, k - );

     //递归构造右子树

     root->r = createTree(posL + numL, posR - , k + , ordR);//取出根节点

     return root;

 }

 void getResBFS(Node* root)

 {

     queue<Node*>q;

     Node* p = nullptr;

     q.push(root);

     cout << root->val;

     while (!q.empty())

     {

         p = q.front();

         if (p != root)

             cout << " " << p->val;

         q.pop();

         if (p->l != nullptr)

             q.push(p->l);

         if (p->r != nullptr)

             q.push(p->r);

     }

     cout << endl;

 }

 int main()

 {

     int N;

     cin >> N;

     pos = new int[N];

     ord = new int[N];

     for (int i = ; i < N; ++i)

         cin >> pos[i];

     for (int i = ; i < N; ++i)

         cin >> ord[i];

     Node* root = createTree(, N - , , N - );

     getResBFS(root);

     return ;

 }