20_100. 相同的树
*题目描述：
解题思路：
- 深度优先搜索：同时遍历这两颗树，比对节点值是否一致，然后比对其左右节点是否相同
- 广度优先搜索：也是同时遍历，使用两个队列存储入队的节点，及时返回错误情况，最后跳出循环时，一定要注意，可能两棵树本身节点数量并不相同。
代码：
深度优先搜索
//深度优先搜索：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
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);
}
}
广度优先搜索
//广度优先搜索：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
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;
// }
Queue queue1 = new LinkedList<>();
Queue queue2 = new LinkedList<>();
queue1.offer(p);
queue2.offer(q);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode tmp1 = queue1.poll();
TreeNode tmp2 = queue2.poll();
if (tmp1.val != tmp2.val) {
return false;
}
TreeNode left1 = tmp1.left;
TreeNode left2 = tmp2.left;
TreeNode right2 = tmp2.right;
TreeNode right1 = tmp1.right;
if (left1 == null ^ left2 == null) {
return false;
}
if (right1 == null ^ right2 == null) {
return false;
}
if (left1 != null) {
queue1.offer(left1);
}
if (left2 != null) {
queue2.offer(left2);
}
if (right1 != null) {
queue1.offer(right1);
}
if (right2 != null) {
queue2.offer(right2);
}
}
return queue1.isEmpty() && queue2.isEmpty();
}
}