给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入：p = [1,2,3], q = [1,2,3]
输出：true
二叉树对比，还是先用递归
递归有三部曲
（1）找整个递归的终止条件：递归应该在什么时候结束？ 节点为null
（2）找返回值：应该给上一级返回什么信息？两个子树是否相同
（3）本级递归应该做什么：在这一级递归中，应该完成什么任务？
如果两个节点都为空，则相同；其中一个为空，则不相同；都不为空，比较值是否相等，相等继续比较左子树和右子树。
此方法又称深度优先遍历/前序遍历
/** * 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) return false; if (q == null) return false; if (p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); else return false; } }
广度优先遍历/层次遍历（非递归）
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { Queue<TreeNode> tmpQueue = new LinkedList<TreeNode>(); tmpQueue.offer(p); tmpQueue.offer(q); while(!tmpQueue.isEmpty()){ p = tmpQueue.poll(); q = tmpQueue.poll(); if(p == null && q == null){ continue; } if((p == null || q == null) || p.val != q.val){ return false; } tmpQueue.offer(p.left); tmpQueue.offer(q.left); tmpQueue.offer(p.right); tmpQueue.offer(q.right); } return true; } }
知识点：
下面是Java中Queue的一些常用方法：
add 添加一个元素 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞
总结：
深度优先遍历：沿着树的深度遍历结点，尽可能深的搜索树的分支。如果当前的节点所在的边都被搜索过，就回溯到当前节点所在的那条边的起始节点。一直重复直到进行到发现源节点所有可达的节点为止。
广度优先遍历：从根节点开始，沿着树的宽度遍历树的节点，直到所有节点都被遍历完为止。