题目描述

二叉树分别以数组存储方式创建、以先序遍历序列创建。输入二叉树的数组存储、先序遍历结果，判断根据它们创建的二叉树是否是同一棵二叉树。

输入

 测试次数t

每组测试数据两行：

第一行：二叉树的数组存储（英文字母表示树结点，#表示空树）

第二行：二叉树的先序遍历结果(英文字母表示树结点，#表示空树）

输出

 对每组测试数据，如果两种方式创建的是同一棵二叉树，输出YES，否则，输出NO。

样例输入

3 ABCDE ABD##E##C## ABC##DE####W##F AB##CDW###E#F## abc##d ab##c#d

样例输出

YES YES NO

#include<iostream> 
#include<string>
#include<queue>
using namespace std;
class BiTreeNode {
public:
	char data;
	BiTreeNode* leftChild;
	BiTreeNode* RightChild;
	BiTreeNode() :leftChild(NULL), RightChild(NULL) {}
	~BiTreeNode() {}
};
class BiTree {
private:
	BiTreeNode* Root;
	int pos;
	string strTree, Tree;
	BiTreeNode* CreateBiTree();
	void Compare();//内部Compare函数 
public:
	BiTree() {};
	~BiTree() {};
	void CreateTree(string TreeArray);
	void Input(string _Tree);//数组存储二叉树输出 
};
void BiTree::CreateTree(string TreeArray) {//函数用于创建二叉树并于数组存储进行比较 
	pos = 0;
	strTree.assign(TreeArray);
	Root = CreateBiTree();
	Compare();
}
BiTreeNode* BiTree::CreateBiTree()
{
	BiTreeNode* T;
	char ch;
	ch = strTree[pos++];
	while(ch){
	if (ch == '#'){
		T = new BiTreeNode();
		T->data='#';
		T->leftChild=NULL;
		T->RightChild=NULL;
	}
	else
	{
		T = new BiTreeNode();
		T->data = ch;
		
		T->leftChild = CreateBiTree();
		T->RightChild = CreateBiTree();
	}
	return T;
}
}
void BiTree::Compare(){
	int i = 0;
	BiTreeNode* p;
	queue<BiTreeNode*> Q;
	Q.push(Root);
	while (i < Tree.length())
	{
		p = Q.front();
		Q.pop();
		if (p) {
			if (p->data != Tree[i])
			{
				cout << "NO" << endl;
				return;//不匹配则结束函数 
			}
			Q.push(p->leftChild);//左子树入队 
			Q.push(p->RightChild);//右子树入队 
		}i++;
	}
	cout << "YES" << endl;//循环完则说明匹配 
}

void BiTree::Input(string _Tree) {
	Tree = _Tree;
}
int main() {
	int t, i;
	cin >> t;
	for (i = 0; i < t; i++) {
		string s1, s2;
		cin >> s1 >> s2;
		BiTree* T = new BiTree();
		T->Input(s1); 
		T->CreateTree(s2);
	}
	return 0;
}