锐客网

  1. 首页 > it技术 > >

PTA|二叉树前序、中序、后序、层次遍历之间的转换

数据结构二叉树pta

PTA：L2-006 树的遍历
题意：中序遍历+后序遍历=>层次遍历
题解：

  • 由算法可知，每次找到后序遍历的最后一个元素即post[pos]，从中序遍历中找到in[mid] = post[post]，mid划分树。
  • 如果按照父节点和儿子结点的关系为2*parent=son，那么数组要开2^n，为了节省空间，不按照此编号。定义全局变量id，dfs返回的是子节点的编号，如果不存在则为-1。
代码：
#include using namespace std; int const N = 30 + 5; int post[N],in[N],n,pos,id; vectorans; struct Node{ int l,r,val; }node[N]; int dfs(int l,int r){ if(l > r)return -1; //返回id int mid = 0; for(int i=l; i<=r; i++){ if(in[i] == post[pos]){ mid = i; break; } } int tid = ++id; node[tid].val = post[pos--]; node[tid].r = dfs(mid + 1,r); node[tid].l = dfs(l,mid - 1); return tid; } void level_dfs(){ queueq; q.push(1); while(!q.empty()){ int p = q.front(); q.pop(); ans.push_back(node[p].val); if(node[p].l != -1) q.push(node[p].l); if(node[p].r != -1) q.push(node[p].r); } for(int i=0; i

PTA：L2-011 玩转二叉树
题意：中序遍历+前序遍历=>反转层次遍历
题解：
  • 思路同上。pos从1开始递增。
  • 层次遍历先考虑右子树，再考虑左子树。
代码：
#include using namespace std; int const N = 30 + 5; int pre[N],in[N],n,pos,id; vectorans; struct Node{ int l,r,val; }node[N]; int dfs(int l,int r){ if(l > r)return -1; //返回id int mid = 0; for(int i=l; i<=r; i++){ if(in[i] == pre[pos]){ mid = i; break; } } int tid = ++id; node[tid].val = pre[pos++]; node[tid].l = dfs(l,mid - 1); node[tid].r = dfs(mid + 1,r); return tid; } void level_dfs(){ queueq; q.push(1); while(!q.empty()){ int p = q.front(); q.pop(); ans.push_back(node[p].val); if(node[p].r != -1) q.push(node[p].r); if(node[p].l != -1) q.push(node[p].l); } for(int i=0; i

PTA：1119Pre- and Post-order Traversals
题意：由前序和后序构造中序遍历，不唯一输出任意一个
题解：
  • 当存在结点只有左子树或者右子树，前序和后序相同，所以不能保证唯一。但是无论是左子树还是右子树对中序遍历的结果并不影响。
  • 【l1，r1】为前序遍历的区间，【l2，r2】为后序遍历的区间
  1. 前序遍历的第一个和后序遍历的最后一个必定相同，即pre[l1] = post[r2]，且为根节点root。
  2. 那么post[r2-1]可能是root的右儿子（结果不唯一时，也有可能是左儿子，我们这里假设是右儿子），在前序遍历数组中找到pre[mid] = post[r2-1]，根据前序遍历的特性，易知【l1+1,mid - 1】是root的左子树，其对应的后序遍历区间为【l2，l2 + lson - 1】，lson = (mid - 1) - (l1 + 1) + 1为左子树的大小。
  3. 同理【mid，r1】为右子树，其对应的后序遍历区间为【l2 + lson，r2 - 1】。
  4. 当出现lson为0，表示结果不唯一，post[r2-1]可能是左儿子，但是我们默认是右儿子，所以步骤二可这样解释。
代码：
#include using namespace std; int const N = 30 + 5; int pre[N],post[N]; int n,flag; vectorans; void solve(int l1,int r1,int l2,int r2){ if(l1 == r1){ ans.push_back(pre[l1]); return; } int mid; for(int i=l1+1; i<=r1; i++){ if(pre[i] == post[r2-1]){ mid = i; break; } } int lson = (mid - 1) - (l1 + 1) + 1; if(lson >= 1) solve(l1 + 1,mid - 1,l2,l2 + lson - 1); else flag = false; ans.push_back(pre[l1]); solve(mid,r1,l2 + lson,r2 - 1); } int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&pre[i]); for(int i=1; i<=n; i++) scanf("%d",&post[i]); flag = true; solve(1,n,1,n); if(flag)printf("Yes\n"); elseprintf("No\n"); for(int i=0; i

【PTA|二叉树前序、中序、后序、层次遍历之间的转换】

    推荐阅读


    上一篇：算法|2022届秋招算法岗将何去何从（）

    下一篇：python|python treemap_Python中的Treemap可视化