Pat 1497 树的遍历

题目

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N 个整数，表示二叉树的层序遍历。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

题解

1. 给定二叉树的中序和后序遍历序列，输出二叉树的层序遍历结果。

   此题中的二叉树结点的权值不一定是0～N之间的值，也可能是10000000等很大的值。

   不能用数组存pos和l,r

     // 设计二叉树存储结构
     vector<int> post_order(N, 0);  	// 存储后序序列
     vector<int> in_order(N, 0);    	// 存储中序序列
     unordered_map<int, int> pos;    // 存储中序序列每个元素的位置
        
     unordered_map<int, int> l, r;// 记录二叉树的左孩子,右孩子
        
     // 构造二叉树
     // 构造过程是一个不断划分的过程， 以root为中心，划分为左右子树
     // il, ir, pl, pr 分别指中序，后序序列的序号
     int buildBiTree(int il, int ir, int pl, int pr)
     {
         int root = postOrder[pr];
         int k = pos[root];
         if (il < k) {
             l[root] = buildBiTree(il, k-1, pl, pl+k-il-1);
         }
         if (ir > k) {
             r[root] = buildBiTree(k+1, ir, pr-(ir-k), pr - 1);
         }
         return root;
     }
        
     // 层序遍历输出结果（借助于队列，其实就是BFS）
     void bfs(int root)
     {
         queue<int> q;
         q.push(root);
         int count = 0;
         while (q.empty() == false) {
             auto node = q.front();
             if (count == 0) {
                 cout << node;
             } else {
                 cout << " " << node;
             }
             count++;
             q.pop();
             if (l.count(node)) {
                 q.push(l[node]);
             }
             if (r.count(node)) {
                 q.push(r[node]);
             }
         }
     }