PAT A1020 Tree Traversals [二叉树后序中序求层序]

客官°小女子只卖身不卖艺 2021-10-23 15:48 230阅读 0赞

## 题目描述 ##

[链接][Link 1]  
给定后序和中序，求层序结果

## 分析 ##

*  递归实现，这里给出先序和后序，求中序的
 *  递归：考虑中间过程
    
     *  先序\\(\[preL,preR\]\\) 中序\\(\[inL,inR\]\\)
     *  根节点：\\(preL\\)
     *  中序根节点：\\(k,a\[k\]==a\[preL\]\\) 遍历可得到
     *  中序左子树结点个数：\\(k-inL\\) ，左子树序列\\(\[inL,k-1\]\\)
     *  先序左子树序列\\(\[preL+1,preL+k-inL\]\\)
     *  中序右子树结点个数：\\(inR-k\\) , 右子树序列\\(\[k+1,inR\]\\)
     *  先序右子树序列:\\(\[preL+k-inL+1,preR\]\\)
     *  函数状态\\((preL,preR,inL,inR)\\)
 *  终止：先序长度小于等于0，即\\(preR-preL<0\\)
 *  具体里面的操作：每次递归，得到根节点的值，就可以生成一个根节点，具体怎么挂上去呢？可以把函数返回值写成一个指针，然后回溯的时候就可以挂上去了。最后返回的就是整个树的根

#include<bits/stdc++.h> using namespace std; struct node{ int data; node *lchild; node *rchild; }; const int maxn = 100; int post[maxn], in[maxn]; node *create(int postL, int postR, int inL, int inR){ if(postL > postR) return NULL; int k; for(k=inL;k<=inR;k++){ if(in[k] == post[postR]) break; } int cnt = k-inL; node *root = new node; root->data = post[postR]; root->lchild = create(postL, postL+cnt-1, inL, k-1); root->rchild = create(postL+cnt, postR-1, k+1, inR); return root; } vector<int> ans; void layerOrder(node *root){ queue<node*> q; q.push(root); while(!q.empty()){ node *now = q.front(); ans.push_back(now->data); q.pop(); if(now->lchild) q.push(now->lchild); if(now->rchild) q.push(now->rchild); } } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>post[i]; } for(int i=0;i<n;i++){ cin>>in[i]; } node *root = create(0, n-1, 0, n-1); layerOrder(root); for(int i=0;i<ans.size();i++){ if(i==0) cout<<ans[i]; else cout<<" "<<ans[i]; } cout<<endl; }

转载于:https://www.cnblogs.com/doragd/p/11266568.html

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072