题目
给你两棵二叉树的根节点 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
解题
方法一：BFS
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not (p or q): return True if not (p and q): return False queue_p = collections.deque([p]) queue_q = collections.deque([q]) while queue_p and queue_q: cur_p = queue_p.popleft() cur_q = queue_q.popleft() if not (cur_p or cur_q): continue if not cur_p or not cur_q or cur_p.val!=cur_q.val: return False queue_p.append(cur_p.left) queue_q.append(cur_q.left) queue_p.append(cur_p.right) queue_q.append(cur_q.right) return True
c++解法
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(!(p||q)) return true; if(!(p&&q)) return false; queue<TreeNode*> queue_p; queue<TreeNode*> queue_q; queue_p.push(p); queue_q.push(q); while(!queue_p.empty()&&!queue_q.empty()){ TreeNode* cur_p=queue_p.front(); queue_p.pop(); TreeNode* cur_q=queue_q.front(); queue_q.pop(); if(!(cur_p||cur_q)) continue; if(!cur_p||!cur_q||cur_p->val!=cur_q->val) return false; queue_p.push(cur_p->left); queue_q.push(cur_q->left); queue_p.push(cur_p->right); queue_q.push(cur_q->right); } return true; } };
与 就行了
!queue_p.empty()&&!queue_q.empty()
如果一个子树为空一个不为空
这里就会返回false;
if(!cur_p||!cur_q||cur_p->val!=cur_q->val) return false;
java写法
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null&&q==null) return true; if(p==null||q==null) return false; if(p.val!=q.val) return false; return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } }
