给定二叉树的中序遍历和后序遍历，不建树求其层序遍历(PAT A1020)

悠悠 2022-11-20 05:00 112阅读 0赞

一、问题描述  
我这篇博文[经典二叉树遍历问题的总结][Link 1]，留下了一个坑，即**给定二叉树的中序遍历和后序遍历，不建树求其层序遍历**，现来填坑了。

二、中序遍历 + 后序遍历 -> 层序遍历  
既然已经会了(中序遍历 + 后序遍历 -> 前序遍历)，那么在求前序遍历的过程中，给结点附加上index，再把index按小到大排序，此时结点序列正是层序遍历啊

> **总结**：层序遍历不仅可以利用队列 + BFS来求，还可以利用index从小到大的特点来求。

①代码如下：

//给定二叉树的中序遍历和后序遍历，不建树求其层序遍历
    #include<cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct Node
    {
        
        int value, index;
    };
    
    bool cmp(Node a, Node b) {
        
        return a.index < b.index;
    }
    
    void preOrder(vector<Node>& ans, const vector<int>& inorder, int headI, int tailI, const vector<int>& postorder, int headP, int tailP, int index) {
        
        
        if(headI > tailI)
            return;
        int mid = -1;
        for (int i = headI; i <= tailI; i++) {
        
            if(inorder[i] == postorder[tailP]) {
        
                mid = i;
                break;
            }
        }
        int leftTreeNodeNumber = mid - headI;
        //前序遍历
        ans.push_back({
        postorder[tailP], index});
        //左子树
        preOrder(ans, inorder, headI, mid - 1, postorder, headP, headP + leftTreeNodeNumber - 1, 2 * index);
        //右子树
        preOrder(ans, inorder, mid + 1, tailI, postorder, headP + leftTreeNodeNumber, tailP - 1, 2 * index + 1);
        return;
    }
    
    void Print(vector<Node>& ans) {
        
        sort(ans.begin(), ans.end(), cmp);
        int count = ans.size();
        for (int i = 0; i < count; i++) {
        
            if(i == 0)
                printf("{");
            else
                printf(", ");
            printf("%d", ans[i].value);
        }
        printf("}\n");
    }
    
    int main() {
        
        vector<int> inorder = {
        1, 2, 3, 4, 5, 6, 7}, postorder = {
        2, 3, 1, 5, 7, 6, 4};
        vector<Node> ans;
        int index = 1;
        preOrder(ans, inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, index);
        Print(ans);
        return 0;
    }

②层序遍历结果如下：  
![在这里插入图片描述][20201107151359949.png_pic_left]  
三、同理 : 中序遍历 + 前序遍历 -> 层序遍历  
虽然给了前序遍历，但仍然需要前序遍历过程来给结点附上index。  
①代码如下：

//给定二叉树的中序遍历和前序遍历，不建树求其层序遍历
    #include<cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct Node
    {
        
        int value, index;
    };
    
    bool cmp(Node a, Node b) {
        
        return a.index < b.index;
    }
    
    void preOrder(vector<Node>& ans, const vector<int>& inorder, int headI, int tailI, const vector<int>& pretorder, int headP, int tailP, int index) {
           
        if(headI > tailI)
            return;
        int mid = -1;
        for (int i = headI; i <= tailI; i++) {
        
            if(inorder[i] == pretorder[headP]) {
        
                mid = i;
                break;
            }
        }
        int leftTreeNodeNumber = mid - headI;
        //前序遍历
        ans.push_back({
        pretorder[headP], index});
        //左子树
        preOrder(ans, inorder, headI, mid - 1, pretorder, headP + 1, headP + leftTreeNodeNumber, 2 * index);
        //右子树
        preOrder(ans, inorder, mid + 1, tailI, pretorder, headP + leftTreeNodeNumber + 1, tailP, 2 * index + 1);
        return;
    }
    
    void Print(vector<Node>& ans) {
        
        sort(ans.begin(), ans.end(), cmp);
        int count = ans.size();
        for (int i = 0; i < count; i++) {
        
            if(i == 0)
                printf("{");
            else
                printf(", ");
            printf("%d", ans[i].value);
        }
        printf("}\n");
    }
    
    int main() {
        
        vector<int> inorder = {
        1, 2, 3, 4, 5, 6, 7}, preorder = {
        4, 1, 3, 2, 6, 5, 7};
        vector<Node> ans;
        int index = 1;
        preOrder(ans, inorder, 0, inorder.size() - 1, preorder, 0, preorder.size() - 1, index);
        Print(ans);
        return 0;
    }

②层序遍历结果如下：  
![在这里插入图片描述][20201107151359949.png_pic_left]  
四、PAT A1020 Tree Traversals (25分)  
1.题目  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]  
2.AC代码

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct Node {
        
        int index, data;
    };
    vector<int> postO, inO;
    vector<Node> V;
    void preOrder(int tRoot, int tStart, int tEnd, int tIndex) {
        
        if(tStart > tEnd) return;
        int k = tStart;
        while(k <= tEnd && inO[k] != postO[tRoot]) k++;
        V.push_back({
        tIndex, postO[tRoot]});
        int numR = tEnd - k;
        preOrder(tRoot - 1 - numR, tStart, k - 1, 2 * tIndex + 1);
        preOrder(tRoot - 1, k + 1, tEnd, 2 * tIndex + 2);
    }
    bool cmp (Node a, Node b) {
        
        return a.index < b.index;
    }
    int main() {
        
        int n;
        cin >> n;
        postO.resize(n);
        inO.resize(n);
        for(int i = 0; i < n; i++) cin >> postO[i];
        for(int i = 0; i < n; i++) cin >> inO[i];
        preOrder(n - 1, 0, n - 1, 0);
        sort(V.begin(), V.end(), cmp);
        for(int i = 0; i < n; i++) {
        
            if(i > 0) printf(" ");
            cout << V[i].data;
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_37477009/article/details/109542759
[20201107151359949.png_pic_left]: /images/20221120/ad2fc1741fe148829b911e3c73caa65d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6c6d88e4bbf44232a257e693deae6b73.png