L2-006 树的遍历-团体程序设计天梯赛GPLT

淡淡的烟草味﹌ 2023-07-07 13:59 15阅读 0赞

> 题目来源：团体程序设计天梯赛-练习集  
> 题目地址：[L2-006 树的遍历][L2-006]

![problem][]

### 题目大意 ###

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

**预备知识：**  
中序遍历（Inorder Traversal）：先遍历左子树，再访问更节点，最后遍历右子树。  
后续遍历（Postorder Traversal）：先遍历左子树，再遍历右子树，最后访问根节点。  
（注意：遍历子树的时候也要按照相应的的方式遍历。）

我们可以通过一颗二叉树的**前序遍历和中序遍历**或者**后序遍历和中序遍历**来确定一颗二叉树。

### 题目分析 ###

我们可以根据它给出的后序遍历和中序遍历，进行二叉树的建树，然后用bfs求出该二叉树的层序遍历，最后输出就可以了。

下面就简单讲一下，怎么通过后序遍历和中序遍历的结果来得出二叉树的结构。

设中序遍历序列为  i n \_ o r d e r e d in\\\_ordered in\_ordered ，其范围为  \[ l a ,   r a \] \[la, \\ ra\] \[la, ra\]；后序遍历序列为  p o s t \_ o r d e r e d post\\\_ordered post\_ordered ，其范围为  \[ l b ,   r b \] \[lb, \\ rb\] \[lb, rb\]。

*  根据后续遍历的性质，**可以知道  p o s t \_ o r d e r e d \[ r b \] post\\\_ordered\[rb\] post\_ordered\[rb\] 为根节点**。然后我们**在中序遍历序列  i n \_ o r d e r e d in\\\_ordered in\_ordered 中找出根节点的位置**。
 *  至此，我们已经可以知道  i n \_ o r d e r e d in\\\_ordered in\_ordered 中，左右子树的范围分为别为  \[ l a ,   p − 1 \] \[la,\\ p-1\] \[la, p−1\] 和  \[ p + 1 ,   r a \] \[p+1,\\ ra\] \[p\+1, ra\]。于是，我们就**可以求出左子树的节点个数**：  
     c n t = p − l a cnt=p-la cnt=p−la
 *  接着，我们就可以**求出后序遍历  p o s t \_ o r d e r e d post\\\_ordered post\_ordered 中左右子树的范围**了。有了以上信息，我们就可以**利用同样的方法对求左子树的相关信息，进行递归建树**，进而得到整棵二叉树的结构。

（上述过程的图示）  
![1][]  
有了二叉树结构，层序遍历还不好求？其实没什么好说的，就是一个很普通的bfs，这里就不展开了。

**坑点：**

*  **题目没有给出树节点键值的范围**，如果键值很大，那么用键值作为数组下标存储左右节点位置的方法会导致数组越界，还好本题良心，放了我一马。
 *  题目有明说，**注意输出格式**，看题要认真。

其实这种题目很没营养的，都是同一个套路。你第一次遇到会觉得学到东西了，觉得很开心。第二次遇到就是秒切了，第三次就会厌倦，第四次……

### 代码如下 ###

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 50;
    int n;
    /** * in_order[]表示中序遍历序列 * post_order[]表示后序遍历序列 * tree[]用于存储树形结构 * 其中，tree[i].first表示i节点左孩子编号，tree[i].second表示i号节点右孩子编号 */
    int in_order[maxn], post_order[maxn];
    pair<int, int> tree[maxn];
    /** * [la, ra]表示中序遍历序列的范围 * [lb, rb]表示后序遍历序列的范围 */
    int build(int la, int ra, int lb, int rb) { 
        if (la > ra || lb > rb) return 0;
        int rt = post_order[rb];
        //p表示根节点在中序遍历序列中的位置
        int p = la;
        while (in_order[p] != rt) p++;
        //cnt表示左子树的节点数
        int cnt = p - la;
        //根据已知量，求左右子树所在的遍历序列区间
        tree[rt].first = build(la, p - 1 , lb, lb + cnt - 1);
        tree[rt].second = build(p + 1, ra, lb + cnt, rb - 1);
        return rt;
    }
    
    /** * 利用bfs层序遍历二叉树 * @param root表示二叉树的根节点 */
    void bfs(int root) { 
        vector<int> ans;
        queue<int> q;
        q.push(root);
        while (!q.empty()) { 
            int node = q.front();
            q.pop();
            ans.push_back(node);
            if (tree[node].first) q.push(tree[node].first);
            if (tree[node].second) q.push(tree[node].second);
        }
        int len = ans.size();
        for (int i = 0; i < len; i++)
            cout << ans[i] << (i == len - 1 ? '\n' : ' ');
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> post_order[i];
        for (int i = 1; i <= n; i++)
            cin >> in_order[i];
        int root = build(1, n, 1, n);
        bfs(root);
        return 0;
    }

--------------------

如果本文对你有所帮助，要记得点赞哦~

[L2-006]: https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456
[problem]: https://img-blog.csdnimg.cn/20200224084708905.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200224093010304.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70