100. 相同的树
https://leetcode-cn.com/problems/same-tree/
代码【迭代】
思路:使用队列进行DFS遍历
1、迭代终止条件:一方队列为空时,结束迭代过程
2、迭代搜索过程:
- 先弹出两个队列中的首元素node1与node2
- 若p.val != q.val,则返回false
- 接下来判断node1与node2的左、右子节点是否一致,不一致则返回false
3、最后,若两个队列都为空,表明二叉树p与q相同,否则不同
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
}
LinkedList<TreeNode> que1 = new LinkedList<>();
LinkedList<TreeNode> que2 = new LinkedList<>();
que1.add(p);
que2.add(q);
while (!que1.isEmpty() && !que2.isEmpty()) {
TreeNode node1 = que1.poll();
TreeNode node2 = que2.poll();
if (node1.val != node2.val) return false;
TreeNode left1 = node1.left;
TreeNode right1 = node1.right;
TreeNode left2 = node2.left;
TreeNode right2 = node2.right;
if ((left1 == null) ^ (left2 == null)) return false;
if ((right1 == null) ^ (right2 == null)) return false;
if (left1 != null) que1.add(left1);
if (right1 != null) que1.add(right1);
if (left2 != null) que2.add(left2);
if (right2 != null) que2.add(right2);
}
return que1.isEmpty() && que2.isEmpty();
}
代码【DFS】
思路:
1、搜索边界:若p == null && q == null,则返回true,否则返回false
2、搜索过程:
- 若p.val != q.val,则返回false
- 否则,继续DFS遍历左子树与右子树
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}