关于算法-数据结构:PAT甲级1020-Tree-Traversals

题目粗心：

给定一个二叉树的后序遍历和中序遍历,要求输入层序遍历

算法思路:

首先由后序遍历和中序遍历构建此二叉树,而后层序遍历二叉树.

构建二叉树的思路：

应用递归建设二叉树，假如递归过程中某步的后序区间是$[beginPost,lastPost]$,中序区间是$[beginIn,lastIn]$,那么根节点为$post[lastPost]$,首先初始化根节点$root$，接着须要在中序遍历中找到根节点的地位$index_root$,而后计算左子树的个数leftTreeLen = index_root-beginIn,这样左子树和右子树在后序和中序遍历中就离开了,紧接着就是左子树递归root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1);
右子树递归root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn);
递归的边界就是在区间长度小于0的时候间接返回空即可。

层序遍历的思路见代码：

void leverTraverse(Node* root){
    queue<Node*> q;
    int num = 0;//输入节点的个数，用来管制空格输入
    q.push(root);
    while (!q.empty()){
        Node* t = q.front();
        q.pop();
        printf("%d",t->data);
        if(num<N-1) printf(" ");
        ++num;
        if(t->left!=nullptr){
            q.push(t->left);
        }
        if(t->right!=nullptr){
            q.push(t->right);
        }
    }
}

留神点：

• 1、应用数组in在本地编译器上可能无奈输出数据，CLion上无奈应用，DEV却能够。
• 2、在子树递归的时候，左右子树的区间肯定得分清，不然会导致递归失败，什么都没有输入，并且还不报错。
• 3、空格的输入须要应用一个变量num统计输入的个数，当num<N-1的时候就输入空格

提交后果：

AC代码：

#include <cstdio>
#include <queue>

using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};

int N;// 节点个数
int post[50],In[50];// 后序和中序遍历序列

Node* createTree(int beginPost,int lastPost,int beginIn,int lastIn){
    if(beginPost>lastPost){
        return nullptr;
    }
    Node* root = new Node;
    root->data = post[lastPost];
    // 首先找到根节点在中序序列的地位
    int index_root;
    for (index_root = beginIn; index_root <= lastIn; ++index_root) {
        if(In[index_root]==root->data){
            break;
        }
    }
    int leftTreeLen = index_root-beginIn;//左子树元素个数
    root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1);
    root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn);
    return root;
}

void leverTraverse(Node* root){
    queue<Node*> q;
    int num = 0;//输入节点的个数，用来管制空格输入
    q.push(root);
    while (!q.empty()){
        Node* t = q.front();
        q.pop();
        printf("%d",t->data);
        if(num<N-1) printf(" ");
        ++num;
        if(t->left!=nullptr){
            q.push(t->left);
        }
        if(t->right!=nullptr){
            q.push(t->right);
        }
    }
}

int main()
{
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        scanf("%d",&post[i]);
    }
    for (int j = 0; j < N; ++j) {
        scanf("%d",&In[j]);
    }
    Node* root = createTree(0,N-1,0,N-1);
    leverTraverse(root);
    return 0;
}