3.5 如何判断两棵二叉树是否相等

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？

分析与解答：

如果两棵二叉树root1、root2相等，那么root1与root2结点的值相同，同时它们的左右孩子也有着相同的结构，并且对应位置上结点的值相等，即root1.data==root2.data，并且root1的左子树与root2的左子树相等，并且root1的右子树与root2的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的递归算法。实现代码如下：

程序的运行结果为

算法性能分析：

这个算法对两棵树只进行了一次遍历，因此，时间复杂度O（n）。此外，这个算法没有申请额外的存储空间。