给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
通过次数323,809提交次数542,092
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//递归法 class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==nullptr&&q==nullptr)return true; if(!p||!q||(p->val!=q->val))return false; bool a=isSameTree(p->left,q->left); bool b=isSameTree(p->right,q->right); bool c=a&&b; return c; } }; //使用queue class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { // if(p==nullptr&&q==nullptr)return true; // if(!p||!q)return false; queue<TreeNode*>qu; qu.push(p); qu.push(q); while(!qu.empty()) { TreeNode* node1 = qu.front(); qu.pop(); TreeNode* node2 = qu.front(); qu.pop(); if(!node1&&!node2)continue; if(!node1||!node2||(node1->val!=node2->val))return false; qu.push(node1->left); qu.push(node2->left); qu.push(node1->right); qu.push(node2->right); } return true; } }; //使用stack ```class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { // if(p==nullptr&&q==nullptr)return true; // if(!p||!q)return false; stack<TreeNode*>qu; qu.push(p); qu.push(q); while(!qu.empty()) { TreeNode* node1 = qu.top(); qu.pop(); TreeNode* node2 = qu.top(); qu.pop(); if(!node1&&!node2)continue; if(!node1||!node2||(node1->val!=node2->val))return false; qu.push(node1->left); qu.push(node2->left); qu.push(node1->right); qu.push(node2->right); } return true; } };
