leetcode543. 二叉树的直径

二叉搜索树

http://www.nowcoder.com/practice/3d6dd9a58d5246f29f71683346bb8f1b

leetcode543. 二叉树的直径

#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;
}
全部评论

相关推荐

兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务