3.5 如何判断两棵二叉树是否相等
【出自BD面试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？
分析与解答：
如果两棵二叉树root1、root2相等，那么root1与root2结点的值相同，同时它们的左右孩子也有着相同的结构，并且对应位置上结点的值相等，即root1.data==root2.data，并且root1的左子树与root2的左子树相等，root1的右子树与root2的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的递归算法。实现代码如下：
程序的运行结果如下：
这两棵树相等
算法性能分析：
这种方法对两棵树只进行了一次遍历，因此，时间复杂度为O（N）。此外，这种方法没有申请额外的存储空间。
