PAT A1020 Tree Traversals

题目链接

解题思路

思路比较简单，就是先根据后序遍历和中序遍历构建一棵二叉树，然后使用bfs层次遍历二叉树即可。

注意

1、创建二叉树使用DFS，但是要注意参数！每次都是找后序遍历最后一个节点作为当前节点的值，然后在中序遍历数组中找到该值，并根据p计算出左右子树的节点个数，然后中序遍历的左右指针l2,r2可以直接用p来表示，但是后序遍历的指针l1,r1,一定要根据左右子树节点个数来确定，比如r1可以是左子树的左指针加上左节点个数减一，右子树的l1可以是右子树左指针加上左子树个数或者是右子树右指针减去右子树个数。总之一定要围绕中序遍历得出的左右节点个数来表示！

2、还有就是要注意传参Node* &root 使用引用是为了在函数内对其修改！

代码

#include <cstdio>
#include <queue>
using namespace std;
const int maxn=50;
struct Node{
    int data;
    Node* left;
    Node* right;
    Node(int d=0,Node* l=NULL,Node* r=NULL):data(d),left(l),right(r){}
};
Node* Root;
int n;
int in[maxn];
int post[maxn];

void create(Node* &root,int l1,int r1,int l2,int r2){
    if(l1>r1||l2>r2) return;
    root=new Node(post[r1]);
    int p=r2;
    while(l2<=p){
        if(in[p]==post[r1]) break;
        p--;
    }
    //p是in数组的坐标，不能直接用于post，需要算出左右子树的节点个数
    create(root->left,l1,l1+p-l2-1,l2,p-1);
    create(root->right,r1-r2+p,r1-1,p+1,r2);
}
void dfs(){
    queue<Node*> q;
    printf("%d",Root->data);
    if (Root->left) q.push(Root->left);
    if (Root->right) q.push(Root->right);
    while(!q.empty()){
        Node* u=q.front();
        q.pop();
        printf(" %d",u->data);
        if (u->left) q.push(u->left);
        if (u->right) q.push(u->right);
    }
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&post[i]);
    for(int i=0;i<n;i++) scanf("%d",&in[i]);
    create(Root,0,n-1,0,n-1);
    dfs();
    return 0;
}