【PTA】树的遍历

电玩女神 2023-07-02 08:27 9阅读 0赞

#### 前言 ####

> 有道无术,术可求;有术无道,止于术

#### 题目重述 ####

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

#### 输入格式： ####

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

#### 输出格式： ####

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

#### 输入样例： ####

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

#### 输出样例 ####

4 1 6 3 5 7 2

#### 题解 ####

根据后序、中序还原二叉树，最后层次遍历输出即可。  
具体可参考  
[二叉树的层次遍历][Link 1]  
[先序遍历中序遍历还原后序][Link 2]:这篇与本题有差异，但是思想相同。

#### C++ AC ####

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        
        int l;
        int r;
    };
    node nds[35];
    int hou[35],zhong[35];
    //构造二叉树
    int build(int i, int j, int k, int h)
    {
        
    
        int m=k;
        int root = hou[j];
    
        while(zhong[m]!=root)
            m++;
        if(m==k)
            nds[root].l=-1;
        else
            nds[root].l=build(i,m-k+i-1,k,m-1);
    
        //如果中序的最后一个是根节点，那说明还原后的右子树是空的
        if(m==h)
            nds[root].r=-1;
        else
            nds[root].r=build(m+j-h,j-1,m+1,h);
    
        return root;
    }
    //二叉树层次遍历
    void BFS(int u)
    {
        
        queue<int> q;
        q.push(u);
        while(!q.empty())
        {
        
            if(nds[q.front()].l!=-1)
            {
        
                q.push(nds[q.front()].l);
            }
            if(nds[q.front()].r!=-1)
            {
        
                q.push(nds[q.front()].r);
            }
            //格式控制
            if(q.front()==u)
            {
        
                cout<<q.front();
            }
            else
            {
        
                cout<<" "<<q.front();
            }
            q.pop();
        }
    }
    int main()
    {
        
        node nd;
        nd.l=-1;
        nd.r=-1;
        int n;
        cin>>n;
        for(int i=0; i<n; i++)
        {
        
            nds[i]=nd;
        }
        for(int i=0; i<n; i++)
        {
        
            cin>>hou[i];
        }
        for(int i=0; i<n; i++)
        {
        
            cin>>zhong[i];
        }
        int root = build(0,n-1,0,n-1);
        BFS(root);
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43889841/article/details/98995314
[Link 2]: https://blog.csdn.net/weixin_43889841/article/details/96907208