NC315. 相同的二叉树
描述
示例1
输入:
{1,2,1},{1,#,2}
输出:
false
说明:
示例2
输入:
{1,2,1},{1,2,1}
输出:
true
说明:
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-07-07
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
bool isSameTree(TreeNode* root1, TreeNode* root2) {
// write code here
if(root1 && root2 && root1->val != root2->val) return false;
if(root1==nullptr && root2 != nullptr) return false;
if(root1!=nullptr && root2 == nullptr) return false;
if(!root1 && !root1) return true;
queue<TreeNode*>q1;
queue<TreeNode*>q2;
q1.push(root1);
q2.push(root2);
while(!q1.empty() && !q2.empty())
{
TreeNode* p1 = q1.front();
TreeNode* p2 = q2.front();
q1.pop();
q2.pop();
if(p1->left && p2->left && p1->left->val==p2->left->val)
{
q1.push(p1->left);
q2.push(p2->left);
}
else if(p1->left && p2->left && p1->left->val!=p2->left->val)
return false;
if(p1->right && p2->right && p1->right->val==p2->right->val)
{
q1.push(p1->right);
q2.push(p2->right);
}
else if(p1->right && p2->right && p1->right->val!=p2->right->val)
return false;
}
if(q1.empty() && q2.empty())
return true;
else
return false;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-03-05
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
bool order(TreeNode* &root1, TreeNode* &root2){
if(root1 == nullptr && root2 ==nullptr)return true;
if(root1 == nullptr || root2 ==nullptr)return false;
if(root1->val==root2->val && order(root1->left, root2->left) && order(root1->right, root2->right)){
return true;
}
return false;
}
bool isSameTree(TreeNode* root1, TreeNode* root2) {
// write code here
return order(root1, root2);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-08-06
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
int judge(TreeNode *root)
{
return(root==NULL)?0:1;
}
bool isSameTree(TreeNode* root1, TreeNode* root2) {
vector<vector<int>>res;
queue<TreeNode *>q;
if(root1==NULL&&root2==NULL)return true;
if(judge(root1)!=judge(root2))return false;
q.push(root1);
q.push(root2);
while(!q.empty())
{
int n=q.size()/2;
vector<int>temp;
for(int i=0;i<n;i++)
{
TreeNode *leef=q.front();q.pop();
TreeNode *leef2=q.front();q.pop();
if(leef->val!=leef2->val)return false;//值不一样
if(judge(leef->left)!=judge(leef->left))return false;//结构不一样
if(judge(leef->right)!=judge(leef->right))return false;//结构不一样
if(leef->left&&leef2->left)
{
q.push(leef->left);
q.push(leef2->left);
}
if(leef->right&&leef2->right)
{
q.push(leef->right);
q.push(leef2->right);
}
}
}
return true;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-05-04
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
bool isSameTree(TreeNode* root1, TreeNode* root2) {
// write code here
if(root1==nullptr&&root2==nullptr){
return true;
}
if(root1==nullptr||root2==nullptr){
return false;
}
if(root1->val!=root2->val) return false;
return isSameTree(root1->left, root2->left)&&isSameTree(root1->right, root2->right);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-03-17
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
bool isSameTree(TreeNode* root1, TreeNode* root2) {
// write code here
if(root1==NULL&&root2==NULL){
return true;
}
if(root1==NULL||root2==NULL){
return false;
}
if(root1->val==root2->val){
return isSameTree(root1->left, root2->left)&&isSameTree(root1->right, root2->right);
}else{
return false;
}
}
};