HDU 1710-Binary Tree Traversals(二进制重建)
二进制 HDU Tree Binary 重建
2023-09-14 09:08:09 时间
Binary Tree Traversals
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3340 Accepted Submission(s): 1500
Problem Description
A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed
or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.
In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.
In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.
In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.
Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.
In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.
In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.
In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.
Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.
Input
The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume
they are always correspond to a exclusive binary tree.
Output
For each test case print a single line specifying the corresponding postorder sequence.
Sample Input
9 1 2 4 7 3 5 8 9 6 4 7 2 1 8 5 9 3 6
Sample Output
7 4 2 8 9 5 6 3 1今天刷二叉树专题,搞了半天最终对重建有了一点认识,首先说一下由先序和中序重建二叉树,大体思路是大概是这种:由于先序(pre)的第一个字母肯定是根节点。所以要在中序(ins)序列中找到根节点的位置k,然后递归重建根节点的左子树和右子树。此时要把左子树和右子树当成根节点,然后表示出它们的位置,左子树非常好说,pre+1就是它的位置。对于右子树来说,pre+k+1为它的位置。如图对于由中序和后序重建,思路跟上面大体一样,详细写法有点区别。这个就要在中序序列中找到后序的最后一个字母(即根节点),然后递归重建左子树和右子树,依然是把左子树和右子树当成根节点。左子树的位置为pos+k-1,但传的參数应该是pos (由于我们要找的字母是pos[n-1]),而右子树的位置在后序的倒数第二个字母。传參数为pos+k。(不是pos+k+1,想明确这个就算真明确了)另为这篇没写由后序和中序重建的代码,曾经写过,在这点击打开链接#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cctype> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> #include <list> using namespace std; const int INF=1<<27; const int maxn=5100; typedef struct node { int data; node *l,*r; }*T; void rbuild(T &root,int *pre,int *ins,int n) { if(n<=0) root=NULL; else { root=new node; int k=find(ins,ins+n,pre[0])-ins; root->data=pre[0]; rbuild(root->l,pre+1,ins,k); rbuild(root->r,pre+k+1,ins+k+1,n-k-1); } } int ans[maxn],p; void last(T root) { if(root) { last(root->l); last(root->r); ans[p++]=root->data; } } int main() { int n,i; while(cin>>n){ T root;int pre[maxn],ins[maxn]; for(i=0;i<n;i++) cin>>pre[i]; for(i=0;i<n;i++) cin>>ins[i]; rbuild(root,pre,ins,n); p=0; last(root); for(i=0;i<p;i++) if(i!=p-1) cout<<ans[i]<<" "; else cout<<ans[i]<<endl; } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- png格式 二进制存储方式
- Java实现 蓝桥杯 算法训练 二进制数数
- 十六进制字节 & 十六进制转二进制
- 重新点亮linux 命令树————二进制安装[十一八]
- Centos7 k8s v1.5.2二进制部署安装-dashboard--WEB管理
- LeetCode-67. 二进制求和【位运算,字符串,数学,模拟】
- Leetcode1091. 二进制矩阵中的最短路径(medium)
- 浮点数的二进制表示
- Atitit 文件读取规范 目录 1.1. 以fgetss取代fgets读取一行并过滤掉 HTML 和 PHP 标记。1 1.2. 3. 以二进制读取 fread取代fgets1 1.3. 4.
- atitit.二进制数据无损转字符串网络传输
- 华为OD机试 - 二进制差异数(Java & JS & Python)
- k7.第二章 基于二进制包安装kubernetes v1.21 --集群部署
- k5.第二章 基于二进制包安装kubernetes v1.20 -- 集群部署(三)
- 「程序员上下50年」计算机凭啥用二进制
- Kubernetes 部署一套高可用集群(二进制,v1.18)上
- a19.ansible 生产实战案例 -- docker基于二进制安装harbor-https方式 roles