首页 > 代码库 > HDU 1710Binary Tree Traversals(已知前序中序,求后序的二叉树遍历)
HDU 1710Binary Tree Traversals(已知前序中序,求后序的二叉树遍历)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1710
解题思路:可以由先序和中序的性质得到 : 先序的第一个借点肯定是当前子树的根结点, 那么在
中序中找到这个结点, 则这个结点左边的节点属于左子树, 右边的属于右子树。然后递归遍历就可以了。
样例:
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
7 4 2 8 9 5 6 3 1
如图:
因此,用深搜就能轻松解决了,注意DFS中的变量,以及向清楚DFS的条件,这题就简单多了,具体看代码吧:
#include<iostream> #include<string.h> #include<cstdio> #include<stack> using namespace std; #define maxn 1001 int m,n,a[maxn],b[maxn]; //先序数组和后序数组 stack<int>Q; //存放父节点 void dfs(int l1,int r1,int l2,int r2) {//l1,r1,是先序遍历的数组的开始和末尾,l2,r2是中序遍历的数组的开始和末尾 int i,j; Q.push(a[l1]); //父节点入栈 for(i=l2;i<=r2;i++) if(b[i]==a[l1]) break; //i 父节点在中序遍历的位置,j 左子树和右子树在先序遍历的分界点,即右子树的父节点 j=l1+(i-l2+1); if(j<=r1&&i-1<=r2) dfs(j,r1,i+1,r2); //求解右子树 if(l1+1<=j-1&&l2<=i-1) dfs(l1+1,j-1,l2,i-1); //求解左子树 //不能换位置,根据输出的后序遍历图可以看出,栈的后方为右半部分 } int main() { while(cin>>n) { for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&b[i]); dfs(0,n-1,0,n-1); while(!Q.empty()) { printf("%d",Q.top()); Q.pop(); if(Q.size()) printf(" "); } cout<<endl; } return 0; }
HDU 1710Binary Tree Traversals(已知前序中序,求后序的二叉树遍历)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。