Leetcode Same Tree
3071 ワード
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
考え方:非常に簡単で、広さが遍歴すればいい.判断が煩雑で、左右のノードの値が同じでなければならない.
3.ソリューション2
考え方:やはり再帰的で、遅いです.
http://www.waitingfy.com/archives/1588
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;
}
};
考え方:やはり再帰的で、遅いです.
http://www.waitingfy.com/archives/1588