题目描述
二叉树分别以数组存储方式创建、以先序遍历序列创建。输入二叉树的数组存储、先序遍历结果，判断根据它们创建的二叉树是否是同一棵二叉树。
输入
测试次数t
每组测试数据两行：
第一行：二叉树的数组存储（英文字母表示树结点，#表示空树）
第二行：二叉树的先序遍历结果(英文字母表示树结点，#表示空树）
输出
对每组测试数据，如果两种方式创建的是同一棵二叉树，输出YES，否则，输出NO。
输入样例1
3 ABCDE ABD##E##C## ABC##DE####W##F AB##CDW###E#F## abc##d ab##c#d##
输出样例1
YES YES NO
思路分析
这道题真是让人哭笑不得，我原本写了一个AC代码，就是下面的代码1，然后和同学交流的时候，我突然想到这个代码其实是不满足要求的，能AC纯粹是因为后台测试数据太拉，如果能加上一个三层空树，那么下面这个代码是跑不过的。
下面让我们仰望一下大佬的代码，就是下面的代码2，这是我的学长助教写的，当然我根据他的代码思路写的，不完全一样，但这并不妨碍我们感受其中的美妙，直接根据顺序存储的序列先序遍历还原，然后直接进行比较，NB，orz。
AC代码
代码语言：javascript复制#include <iostream>
#include <string>
#include <queue>
using namespace std;
class BiTreeNode {
public:
char data; //数据域
BiTreeNode *leftChild, *rightChild; //左右子树指针
BiTreeNode() : leftChild(NULL), rightChild(NULL) {}
~BiTreeNode() {}
};
class BiTree {
private:
BiTreeNode *root; //根结点指针
string sTree,order; //建树字符串
int pos; //标识建树字符串的当前字符位置
BiTreeNode *CreateTree() {//建树私有函数
if (pos == sTree.size()) {
return NULL;
} else if (sTree[pos] == '#') {
BiTreeNode *T = new BiTreeNode();
T->data = sTree[pos ];
T->leftChild = NULL;
T->rightChild = NULL;
return T;
}
BiTreeNode *T = new BiTreeNode();
T->data = sTree[pos ];
T->leftChild = CreateTree();
T->rightChild = CreateTree();
return T;
}
public:
BiTree() : root(NULL) {};
void Create(string vArray) {//建树公有接口，参数是特定的先序遍历字符串
pos = 0;
sTree.assign(vArray); //把参数保存到内部字符串
root = CreateTree(); //建树成功后root指向根结点
}
void LevelOrder(BiTreeNode *T) {
queue<BiTreeNode *> open;
BiTreeNode *p = T;
if (p)
open.push(p);
while (!open.empty()) {
p = open.front();
open.pop();
if (p) {
order = p->data;
open.push(p->leftChild);
open.push(p->rightChild);
} else order = '#';
}
}
void Show(string &order) {
LevelOrder(root);
if (order == this->order.substr(0, order.size()))
cout << "YES" << endl;
else cout << "NO" << endl;
}
};
int main() {
int t;
string temp, order;
cin >> t;
while (t--) {
cin >> order >> temp;
BiTree tree;
tree.Create(temp);
tree.Show(order);
}
return 0;
}膜拜大佬代码
代码语言：javascript复制#include <iostream>
using namespace std;
void rebuild(int i, string &test, string &order) {
if (i >= order.size() || order[i] == '#') {
test = '#';
return;
}
test = order[i];
rebuild(2 * i 1, test, order);
rebuild(2 * i 2, test, order);
}
int main() {
int t;
cin >> t;
while (t--) {
string order, pre, test;
cin >> order >> pre;
rebuild(0, test, order);
if (pre == test)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
