二叉树复制和左右子树互换
题目的地址：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1021题目的描述：
二叉树复制和左右子树互换
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:272 测试通过:174
描述
二叉树是非常重要的树形数据结构。复制一棵二叉树是在另一个存储区存放相同的结构和内容，而一棵二叉树上所有左右子树互换是在原存储区上的运算。
请分别根据先序遍历序列建立两棵的二叉树（用#代表空树或空子树），再将这两棵二叉树复制为左右子树建立第三棵二叉树，输出先序和层次遍历序列，最后将第三棵二叉树上所有左右子树互换，并输出先序和层次遍历序列。
输入
共三行
前两行分别对应两棵二叉树的先序遍历序列，用#代表空树或空子树
第三行为第三棵二叉树的根结点。
输出
共四行
前两行为第三棵二叉树生成时的先序、层次遍历序列，
后两行为第三棵二叉树左右子树互换后的先序、层次遍历序列。
样例输入
B # D # #
C E # # F # #
A
样例输出
PreOrder: A B D C E F
LevelOrder: A B C D E F
PreOrder: A C F E B D
LevelOrder: A C B F E D
其实整个题目没有什么难度，算是一道彻底的水题。左右子树的互换涉及到分治法的思想，即如果从根节点开始看，换根节点的左右子树。每个子树的根节点又互换它们的左右子树。那么子问题的解构成了原问题的解。而且与动态规划不同的是，子问题的解是相互独立的，故可以很方便的用递归求解出来。
发现分治和搜索都是递归的（当然也可以写成非递归，但是有点麻烦，本人较懒），而动态规划则会用一个备忘录记录子问题的解，需要时就会使用。故分治和搜索的时间复杂度就会比较高，通常是指数级别（尤其是问题域比较大时，搜索的时间复杂度会非常高，这就需要强剪枝），而动态规划思考非常难，但是一旦写出，时间复杂度会控制在n的平方或n的立方左右。
题目的代码为：
#include<iostream>#include<vector>using namespace std;//二叉树的节点typedef struct node{ char data;struct node *lchild;struct node *rchild; }myNode; vector<myNode*> myV;//创建二叉树myNode* createTree(myNode* root){char ch;cin>>ch;if(ch=='#'){ return root; } root=new myNode();root->data=ch;root->lchild=createTree(root->lchild);root->rchild=createTree(root->rchild); return root;} //先序遍历void preOrder(myNode *root){ if(root!=NULL) { cout<<" "<<root->data; preOrder(root->lchild); preOrder(root->rchild); } } //层次遍历//层次遍历二叉树void levelOrder(myNode *root){ if(root!=NULL) { myV.push_back(root); while(!myV.empty()) { int i; for(i=0;i<myV.size();i++) { myNode *temp=myV; cout<<" "<<temp->data; if(temp->lchild!=NULL) { myV.push_back(temp->lchild); } if(temp->rchild!=NULL) { myV.push_back(temp->rchild); } } //删除 vector<myNode*> newV; for(;i<myV.size();i++) { newV.push_back(myV); } myV=newV; } }} //层层转换左右子树myNode* transform(myNode *root){ if(root!=NULL) { root->lchild=transform(root->lchild); root->rchild=transform(root->rchild); myNode *temp=root->lchild; root->lchild=root->rchild; root->rchild=temp; } return root;} int main(){ myNode *root1=NULL,*root2=NULL,*root3=NULL; root1=createTree(root1); root2=createTree(root2); root3=new myNode(); char ch; cin>>ch; root3->data=ch; root3->lchild=root1; root3->rchild=root2; cout<<"PreOrder:"; preOrder(root3); cout<<endl; cout<<"LevelOrder:"; levelOrder(root3); cout<<endl; root3=transform(root3); cout<<"PreOrder:"; preOrder(root3); cout<<endl; cout<<"LevelOrder:"; levelOrder(root3); cout<<endl; system("pause"); return 0; }
其实不应该使用vector，而应该自己写个队列的，但是实在是不想写，就用现成的stl容器了。天气太热了....
页:
[1]