Same Tree
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.
解法一：递归
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ 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;elsereturn isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}} };
解法二：非递归
建立两个队列分别进行层次遍历，进队时检查对应点是否相等
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool isSameTree(TreeNode *p, TreeNode *q) {if(!isSameNode(p, q))return false;if(!p && !q)return true;queue<TreeNode*> lqueue;queue<TreeNode*> rqueue;lqueue.push(p);rqueue.push(q);while(!lqueue.empty() && !rqueue.empty()){TreeNode* lfront = lqueue.front();TreeNode* rfront = rqueue.front();lqueue.pop();rqueue.pop();if(!isSameNode(lfront->left, rfront->left))return false;if(lfront->left && rfront->left){lqueue.push(lfront->left);rqueue.push(rfront->left);}if(!isSameNode(lfront->right, rfront->right))return false;if(lfront->right && rfront->right){lqueue.push(lfront->right);rqueue.push(rfront->right);}}return true;}bool isSameNode(TreeNode* p, TreeNode *q){if(!p && !q)return true;if((p && !q) || (!p && q) || (p->val != q->val))return false;return true;} };