即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

PAT 1020 Tree Traversals(树重建+BFS)

编程语言 lecholin 21℃ 0评论
本文目录
[隐藏]

1.题目

https://www.patest.cn/contests/pat-a-practise/1020

题意:给定二叉树的后序、中序遍历结果,输出其层次遍历结果

2.解题思路

首先重建树,关于利用含中序的两种序列构建这棵二叉树,详见之前的博客二叉树遍历(已知前中序求后序),最后根据这棵树的层次做输出,一遍BFS就可以解决。

3.AC代码

#include 
#include 
#include 
using namespace std;

const int maxn = 35;
int n, posOrder[maxn], midOrder[maxn];
typedef struct node
{
    int value;
    node *left, *right;
}NODE;

//s1/e1为后序字符串的首尾,s2/e2为中序字符串首尾
NODE* BuildTree(int s1, int e1, int s2, int e2)
{
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->value = posOrder[e1];
    newnode->left = newnode->right = NULL;
    int cmp = posOrder[e1], rootIndex = -1;
    for (int i = s2; i<=e2; ++i) //找到中序序列中的当前根节点对应下标
    {
        if (midOrder[i] == cmp)
        {
            rootIndex = i;
            break;
        }
    }
    //注意下面递归式参数的计算
    if (rootIndex != e2) //该节点有右子树
        newnode->right = BuildTree(e1-(e2-rootIndex), e1-1, rootIndex+1, e2);
    if (rootIndex != s2) //该节点有左子树
        newnode->left = BuildTree(s1, e1-(e2-rootIndex)-1, s2, rootIndex-1);

    return newnode;
}

void BFS(NODE *root)
{
    vector<int> res;
    queue q;
    NODE tmp;
    q.push(*root);
    while(!q.empty())
    {
        int sz = q.size();
        for (int i = 0; i//遍历当前层结点
        {
            tmp = q.front();
            q.pop();
            res.push_back(tmp.value);
            //由该节点产生下一层的结点
            if (tmp.left != NULL)
                q.push(*tmp.left);
            if (tmp.right != NULL)
                q.push(*tmp.right);
        }
    }
    for (int i = 0; i < res.size(); ++i) //层次输出
    {
        cout << res[i];
        if (i != res.size()-1)
            cout << ' ';
        else cout << endl;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; icin >> posOrder[i];
    for (int i = 0; icin >> midOrder[i];
    NODE* root = BuildTree(0, n-1, 0, n-1);
    BFS(root);
    return 0;
}

转载请注明:CodingBlog » PAT 1020 Tree Traversals(树重建+BFS)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情