Contents
1.题目
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
2.解决方案1
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(!p && !q)
return true;
else if(!p && q)
return false;
else if(p && !q)
return false;
else
{
if(p->val != q->val)
return false;
else
{
queue<TreeNode*> lq;
queue<TreeNode*> rq;
lq.push(p);
rq.push(q);
while(!lq.empty() && !rq.empty())
{
TreeNode* lfront = lq.front();
TreeNode* rfront = rq.front();
lq.pop();
rq.pop();
if(!lfront->left && !rfront->left)
;// null
else if(!lfront->left && rfront->left)
return false;
else if(lfront->left && !rfront->left)
return false;
else
{
if(lfront->left->val != rfront->left->val)
return false;
else
{
lq.push(lfront->left);
rq.push(rfront->left);
}
}
if(!lfront->right && !rfront->right)
;// null
else if(!lfront->right && rfront->right)
return false;
else if(lfront->right && !rfront->right)
return false;
else
{
if(lfront->right->val != rfront->right->val)
return false;
else
{
lq.push(lfront->right);
rq.push(rfront->right);
}
}
}
return true;
}
}
}
};思路：非常简单，广度遍历即可，就是判断比较繁琐，要左右节点的值都要相同才行。
3.解决方案2
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p == NULL && q == NULL)
return true;
else if(p == NULL || q == NULL)
return false;
bool isleftTreeSame = isSameTree(p->left, q->left);
bool isrightTreeSame = isSameTree(p->right,q->right);
return p->val == q->val && isleftTreeSame && isrightTreeSame;
}
};思路：还是递归，比较慢。
1588
