习题10.1二叉搜索树（浙大）

习题10.1二叉搜索树（浙大）

生成两个二叉搜索树，然后按照遍历二叉树的方法判断两个序列生成的二叉树是否相同

#include<vector>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) :val(x), left(nullptr), right(nullptr){}
};

//生成排序二叉树
TreeNode* insertBST(TreeNode* root, int x) {
	if (root == nullptr) {
		root = new TreeNode(x);
		return root;
	}
	if (x < root->val) {
		root->left = insertBST(root->left, x);
	}
	else if (x > root->val) {
		root->right = insertBST(root->right, x);
	}
	return root;
}

//判断两个排序二叉树是否相同
bool isSameBst(TreeNode* root1, TreeNode* root2) {
	if (root1 == nullptr && root2 == nullptr) {
		return true;
	}
	else if ((root1 == nullptr && root2 != nullptr) || (root1 != nullptr && root2 == nullptr)) {
		return false;
	}
	int val1 = root1->val;
	int val2 = root2->val;
	if (val1 != val2)
		return false;
	if (isSameBst(root1->left, root2->left) == false || isSameBst(root1->right, root2->right) == false) {
		return false;
	}
	return true;
}

int main() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	TreeNode* root1 = nullptr;
	//1. build BST
	for (int i = 0; i < str.size(); i++) {
		root1 = insertBST(root1, (int)str[i]);
	}
	//2. 判断新序列是否为二叉树
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		TreeNode* root2 = nullptr;
		for (int i = 0; i < s.size(); i++) {
			root2 = insertBST(root2, (int)s[i]);
		}
		if (isSameBst(root1, root2)) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}