首页 > 代码库 > L2-011. 玩转二叉树
L2-011. 玩转二叉树
L2-011. 玩转二叉树
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:7 1 2 3 4 5 6 7 4 1 3 2 6 5 7输出样例:
4 6 1 7 5 3 2
分析:1.知二叉树中序遍历、前序遍历,生成二叉树 2.二叉树层次遍历(镜面反转即递归时 先操作右子树,在操作左子树)
http://blog.csdn.net/overload1997/article/details/51907884
1 ///L2-011. 玩转二叉树 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #include<cstdio> 6 using namespace std; 7 bool fist; 8 const int maxn=40; 9 struct tree_node 10 { 11 int value; 12 tree_node* leftchild; 13 tree_node* rightchild; 14 tree_node() 15 { 16 leftchild=NULL; 17 rightchild=NULL; 18 } 19 }; 20 /** 21 根据中序遍历,前序遍历建树 22 递归 忽略细节 深入至所有结点建立 23 */ 24 tree_node* build_tree(int pre[],int in[],int length) 25 { 26 if(length==0)return NULL;///终止条件 27 tree_node* temp = new tree_node; 28 int pos; 29 for(pos=0;pos<length;pos++)///找到根节点->然后根据中序遍历把左子树和右子树分开 30 { 31 if(in[pos]==pre[0])break; 32 } 33 temp->value=http://www.mamicode.com/pre[0]; 34 temp->leftchild=build_tree(pre+1,in,pos); 35 temp->rightchild=build_tree(pre+pos+1,in+pos+1,length-pos-1); 36 return temp; 37 } 38 /** 39 层次遍历镜面输出 40 */ 41 void dfs(tree_node* tree) 42 { 43 queue<tree_node*>Q; 44 while(!Q.empty())Q.pop();///置空队列 45 Q.push(tree); 46 tree_node* root; 47 while(!Q.empty()) 48 { 49 root=Q.front(); 50 Q.pop(); 51 if(!fist)///根节点输出 52 { 53 cout<<root->value; 54 fist=true; 55 } 56 else cout<<" "<<root->value; 57 58 if(root->rightchild!=NULL)///先右后左即镜面输出 59 { 60 Q.push(root->rightchild); 61 } 62 if(root->leftchild!=NULL) 63 { 64 Q.push(root->leftchild); 65 } 66 } 67 cout<<endl; 68 } 69 int main() 70 { 71 int n; 72 int pre[maxn],in[maxn]; 73 while(scanf("%d",&n)==1) 74 { 75 fist=false; 76 ///input 77 for(int i=0;i<n;i++)scanf("%d",&in[i]); 78 for(int i=0;i<n;i++)scanf("%d",&pre[i]); 79 ///solve 80 tree_node* tree=build_tree(pre,in,n); 81 dfs(tree); 82 } 83 }
L2-011. 玩转二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。