PAT 1020 Tree Traversals (25分) 解读

Scroll Down

题目

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 (≤30), 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

==说白了就是,给你一棵二叉树的后序遍历结果和中序遍历结果,让你输出这棵二叉树的层序遍历结果。==

题解:

我们应该都接触过由中序遍历和先序遍历得到后序遍历,或者由中序遍历和后序遍历得到先序遍历,其实只要你根据给出的两个序列重构出这棵二叉树,层序遍历也就得到了。

但重构二叉树需要自己创建二叉树的数据结构,还要造一棵树出来,其中指针操作又容易出错,我不想创建树可以吗?可以的!题目只是让我输出最后的遍历结果,又不是让我得到一棵树,我只需要巧妙的调整一下代码就能利用一个map<int, int>得到层序遍历的结果(柳婼大神nb

但不管怎么样,都得先解决一个问题,就是利用中序序列和后序序列怎么得到二叉树呢?这里我简单说一下吧,相信大多数人都会这个操作的。

给个例子:

中序遍历: A D E F G H M Z

后序遍历: A E F D H Z M G

画树求法:
第一步,根据后序遍历的特点,我们知道后序遍历最后一个结点即为根结点,即根结点为G。

第二步,观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。

第三步,根据后序遍历(左右中)的特点,后序遍历中,根G的左边的节点M必然是它的右子树HMZ的根。

第四步,右子树HMZ有三个节点,根G往左移三个位置后D必然是它的左子树的根

第五步,观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下:

1 确定根,确定左子树,确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 返回或者打印当前根。

层序遍历

那我们一般是怎么是层序遍历,宽度优先遍历,层序其实也就是按顺序,一般都是用一个队列,队列中保存的始终是一整层的姐弟啊,对于每层每个节点,访问自己,把左右孩子加入队列,==【保证了访问的先后顺序】==

我们这里采用键值对map<int, int>的形式保存,值:节点值,键:层序遍历下它实际的访问序号(下标),对于每个节点,假如编号是i,那么它的左孩子编号是2 * i,右孩子编号是 2*i+1因为键值的大小关系,map会自动按其顺序排序,相当于保证了访问的先后顺序,这样我们最后直接按顺序输出整个map的值,就实现了队列的功能。

但是因为 我们的序列是数组,下标是从0开始的,所以为了避免 2 * 0 = 0节点值覆盖,我们左孩子编号是 2*i+1,右孩子编号是 2*i+2,当然你可以选择让根节点编号是1,就不会有这个问题。

代码实现

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// 后续遍历,中序遍历
vector<int> postorder, inorder;
// 层序遍历
map<int, int> level_order;

// 因为层序其实也就是按顺序,一般都是用一个队列,对于每层节点,访问自己,把左右孩子加入队列,【保证了访问的先后顺序】
// 我们这里采用键值对<int, int>的形式保存,值:节点值,键:层序遍历下它实际的访问序号(下表)
// 对于每个节点,假如编号是i,那么它的左孩子编号是2 * i,有孩子编号是 2 * i + 1
// 但是因为 我们的下标是从0开始的,所以为了避免 2 * 0 = 0, 我们左孩子编号是 2*i+1,有孩子编号是 2*i+2
// 这样,因为键值的大小关系,map会自动按其顺序排序,相当于保证了访问的先后顺序,这样我们最后直接输出map即可

/**
 * in_start 当前子树中序遍历序列在 inorder数组中的起始位置
 * in_end 当前子树中序遍历序列在 inorder数组中的结束位置
 * post_index 当前子树树根在 postorder数组中的下标
 * 
 * 我们在递归时,每次找到的都是当前树根,然后分别去它的左右子树递归
 * 所以我们增加参数 index 保存当前找到的 树根 按层序遍历时它实际的编号(第几个访问),
 * 在进入它的左子树时,编号就成了 2  * inedx + 1,递归右子树时 编号就成了 2 * index + 2
 */
void Preorder(int in_start, int in_end, int post_end, int index) {
    // 当前子树构建完毕,返回
    if (in_start > in_end) return;
    int i = in_start;
    // post_end总是表示当前子树树根在整棵树后序遍历数组中的下标
    // 找到当前子树树根在中序遍历序列中的位置
    while (i <= in_end && inorder[i] != postorder[post_end]) i++;
    // i 把 [in_start, in_end]划分为 [in_start, i - 1] [i + 1, in_end]两部分
    // 其中 [in_start, i - 1] 是当前树根的左子树的中序遍历序列在整棵树的中序遍历序列inorder中的范围
    // 其中 [i + 1, in_end] 是当前树根的右子树的中序遍历序列在整棵树的中序遍历序列inorder中的范围
    // 根据后续遍历特点(左右中)  x x x x x root,当前子树的根是 root,那么 root前一位置就是当前子树的右子树的根
    // 加入 右子树有 n个节点,那么 root 往左 n 个位置就是 左子树的树根
    level_order[index] = postorder[post_end];
    Preorder(in_start, i - 1, post_end - 1 - (in_end - i), 2 * index + 1);
    Preorder(i + 1, in_end, post_end - 1, 2 * index + 2);
}

int main() {

    // n个节点
    int n;
    cin >> n;
    // 重新分配大小
    postorder.resize(n);
    inorder.resize(n);
    // 读入后序遍历结果
    for (int i = 0; i < n; ++i) cin >> postorder[i];
    // 读入中序遍历结果
    for (int i = 0; i < n; ++i) cin >> inorder[i];
    // 得到层序
    Preorder(0, n - 1, n - 1, 0);
    // 遍历,注意输出格式,末尾不能有多余空格
    auto it = level_order.begin();
    cout << it->second;
    while (++it != level_order.end())
            cout << " " << it->second;
    return 0;
}

我的代码其实就是看完柳婼大神的博客后写的,只是她的题解思路很简洁,我的脑子不太够用,就往详细的写了写,如果大家看着繁琐就直接去访问柳神的博客吧!