网站建设及推广/南昌seo网站推广

给两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

如下面的两颗二叉树：结构相同，而且对应节点的值是相同的

 如下面的二叉树，结构不同，所以不能算为是相同的二叉树

再比如下面的二叉树，虽然结构相等，但是值不相等，也不能算为相同的二叉树

 详细题解

一、基于递归的解决方法

递归函数

public boolean isSameTree(TreeNode p, TreeNode q) {}

终止条件

（1） p == null && q == null 时，p代表的树和q代表的树是一颗空树，自然是相同的树

（2） p == null || q == null 时，表示树的结构不一样，自然不是相同的树

（3） p.val != q.val时，表示树的结构一样，但是对于的值不相等，不是相同的树

状态转换方程

p代表的树和q代表的树相同，可以转换为 p 与 q相同，同时p.left 代表的树 和 q.left 代表的树相同，同时 p.right 代表的树 和 q.right 代表的树相同。

经过上面的分析，其实代码很好写出来，最终的代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {// p 和 q 代表的树都是空树if(p == null && q == null) return true;// p 和 q 代表的树结构不相同，或者是值不相等if(p == null || q == null || p.val != q.val) return false;// 需同时满足p.left 和 q.left 相同，同时p.right 和 q.right 相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}

二、基于队列的解决方案

其实可以对整颗树执行遍历，按照同样的结构进行遍历，对遍历到的每一个节点都判断是否相等即可，无论采用前序遍历或者是中序遍历或者是后续遍历都是可以的，代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
//定义两个队列Queue<TreeNode> queue_p = new LinkedList<>();queue_p.add(p);Queue<TreeNode> queue_q = new LinkedList<>();queue_q.add(q);while (!queue_p.isEmpty() || !queue_q.isEmpty()) {TreeNode pNode = queue_p.poll();TreeNode qNode = queue_q.poll();if (pNode == null && qNode == null) continue;if (pNode == null || qNode == null || pNode.val != qNode.val) return false;queue_p.add(pNode.left);queue_q.add(qNode.left);queue_p.add(pNode.right);queue_q.add(qNode.right);}return true;}