网站建设要那些收费项,打开一个网站搜索页面跳转js,福州网站建设设计公司,百度竞价外包友情提示#xff1a;这题非常值得自己思考独立做出来#xff0c;请反复确认后再往下拉 1119. Pre- and Post-order Traversals (30) 时间限制400 ms内存限制65536 kB代码长度限制16000 B判题程序Special作者CHEN, YueSuppose that all the keys in a binary tree are distinc… 友情提示这题非常值得自己思考独立做出来请反复确认后再往下拉 1119. Pre- and Post-order Traversals (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Special 作者 CHEN, Yue Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique. Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them. Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space. Output Specification: For each test case, first printf in a line Yes if the tree is unique, or No if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line. Sample Input 1: 7
1 2 3 4 6 7 5
2 6 7 4 5 3 1Sample Output 1: Yes
2 1 6 4 7 3 5Sample Input 2: 4
1 2 3 4
2 4 3 1Sample Output 2: No
2 1 3 4 题意给出树的前序后序遍历输出中序。不能确定时任选一种输出 分析和前中、后中一样我们需要找到前后遍历的特殊点 我最先感觉pre的最后一个5和post的第一个2分别代表mid中最右和最左 然后发现 如果pre的第一个1 和post的最后一个1相等那么1是根节点 _(:з」∠)_接着就迫不及待开始做了一顿骚操作以后我发现还做不了 再看的时候发现虽然单看pre没办法 确定2是1的左子树还是右子树但是1在post中的前一个是3那么3要么是1的左子树要么是1的右子树而pre当中2再过去才是3所以说明2是1的左子树3是1的右子树。那么剩下的4567呢 再确认2和3分开以后4567明显就只能是3的子树 有了这一点就可以开始做了 用递归分治对3的左右子树再分别判断逐步缩小直至确认。以下图做详细说明 1.首先我们发现post(1) 前一位是 3对应到pre(3)当中pre(3)与pre(1)中有间隔。说明2是1的左子树3是1的右子树 2.开始递归在橙色圈中我们可以发现5是3的右子树4是3的左子树 3.post(4)前一位7对应到pre当中与pre(4)中间仍然数字间隔所以6是4的左子树7是4的右子树 4.1的左子树2可以看出左边是1不能用右边则都在3的范围内所以2两个子树为空 5.3的右子树5同上两个子树为空 那么我们要怎么判断有没有唯一解呢如果每一个非叶节点都像上面134一样显然是有唯一解的但是如果题中第二个例子的3它的子树4是与3紧连的中间没有数字隔开这是就无法判断是左子树还是右子树。所以只要当我们发现有某个非叶节点只有一个孩子的时候就可以输出No了 代码 #includeiostream
using namespace std;
int pre[40]{0};
int post[40]{0};
int n,judge1;
struct node {int data;struct node *lchild,*rchild;
};
int find(int a[],int data){for(int i0; in; i)if(a[i] data) return i;
}
struct node *creat(struct node *root, int preStart, int preEnd, int postStart, int postEnd){if(pre[preStart] post[postEnd]){root new struct node();root-data pre[preStart];} if(preStart preEnd || postStart postEnd) return root; int i find(pre, post[postEnd - 1]);//i是root右孩子在pre的索引 int j find(post, pre[preStart 1]);//j是root左孩子在post的索引 if(i - preStart 2) { root-lchild creat(root-lchild, preStart1, i-1, postStart, j);root-rchild creat(root-rchild, i, preEnd, j1, postEnd-1);}else{//其实只剩一种可能即 i preStart1 judge0;root-rchild creat(root-rchild, i, preEnd, j1,postEnd-1);}return root;
}
void midOut(struct node* root){static int cnt0;if(root-lchild) midOut(root-lchild);if(root) cnt 0 ? cout root-data : cout root-data;cnt;if(root-rchild) midOut(root-rchild);
}
int main()
{cinn; for(int i0; in; i)cinpre[i];for(int i0; in; i)cinpost[i];struct node *root;root creat(root, 0, n-1, 0, n-1);judge1? coutYesendl:coutNoendl;midOut(root);coutendl;
} 结尾这题感觉有些可惜因为前面想了很久中间试过很多“奇思妙想”的方法当我想到先确认根再确认左右子树时预估代码要写八九十行而且很繁琐就忍不住看了别人的题解。 结果发现就是这个思路 _(:з」∠)_。 不过那时候没想到递归还在扑哧扑哧上下左右想着点所以弄的很复杂。 不过人家直接数组就记录了mid然后直接输出感觉还是很炫酷。 转载于:https://www.cnblogs.com/childwang/p/8280262.html
