[PAT解题报告] Tree Traversals
给定二叉树的后序和中序遍历,返回它的层序遍历。
分析: (1) 先还原二叉树。 因为节点数很少,我们可以用一个大的全局数组代替指针变量——当然每个节点的左右孩子还是指针变量,只不过它们的值指向大数组里的元素,而不是真正自己从堆里开辟的空间。还原可以递归进行。
后序遍历序列最后一个字符x是根节点  (R)x
中序遍历找到对应的x (A)x(B), 它被切分为(A)、(B)两部分,分别对应左右子树。从后序遍历序列的(R)中切分出(A)和(B)那么长的两段,对应于左右子树的后序遍历序列。然后递归还原左右子树即可。
还原出二叉树,做层序遍历时,只需要进行bfs就可以了。

代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

struct node {
node *left;
node *right;
int x;
};

node a[100];
int m,po[100],in[100];

node* make(int *po, int *in, int length) {
    if (length == 0) {
        return 0;
    }
    node *root = &a[m++];
    int i;
    for (i = 0; in[i] != po[length - 1]; ++i)
    ;
    root->x = in[i];
    root->left = make(po, in, i);
    root->right = make(po + i, in + i + 1, length - 1 - i);
    return root;
}
    
        


int main() {
int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",po + i);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d",in + i);
    }
    node *root = make(po, in, n);
    if (root) {
        bool have = false;
        queue<node *> q;
        q.push(root);
        node *last = root;
        while (!q.empty()) {
            bool out = false;
            node *next;
            while (!out) {
                node *temp = q.front();
                q.pop();
                if (temp == last) {
                    out = true;
                }
                if (temp->left) {
                    q.push(next = temp->left);
                }
                if (temp->right) {
                    q.push(next = temp->right);
                }
                if (have) {
                    putchar(' ');
                }
                else {
                    have = true;
                }
                printf("%d",temp->x);

            }
            last = next;
        }
    }
    puts("");
    return 0;
}
    

原题链接: http://www.patest.cn/contests/pat-a-practise/1020


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 13:45
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议