二叉树复制和左右子树互换
题目的地址：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的立方左右。
题目的代码为：
其实不应该使用vector，而应该自己写个队列的，但是实在是不想写，就用现成的stl容器了。天气太热了....
