Leetcode Same Tree
來源：程序員人生 發布時間：2015-04-08 08:21:25 閱讀次數：2632次
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;
}
};
思路：還是遞歸，比較慢。
http://www.waitingfy.com/archives/1588
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
