如何判断两棵二叉树是否相等
猿媛之家
已推送大量原创内容
已出版：
C、java、python、go、php、js、kotlin、scala、c#
等各种语言的面试笔试知识点书籍
已在菜单栏开源持续更新分类整理，干货满满
三步加星，方便阅读
本题来源：百度面试题
难度指数：3 考察频率：4
题目描述：
两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？
分析与解答：
如果两棵二叉树root1、root2相等，那么root1与root2结点的值相同，同时它们的左右孩子也有着相同的结构，并且对应位置上结点的值相等，即root1.data==root2.data，并且root1的左子树与root2的左子树相等，并且root1的右子树与root2的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的递归算法。实现代码如下：
public class Test{/*** 方法功能：判断两棵二叉树是否相等** 参数：root1与root2分别为两棵二叉树的根结点** 返回值：true:如果两棵树相等则返回true，否则返回false*/public static boolean isEqual(BiTNode root1,BiTNode root2){if(root1==null&&root2==null)return true;if(root1==null||root2==null)return false;if(root1.data == root2.data)return isEqual(root1.lchild,root2.lchild) &&isEqual(root1.rchild,root2.rchild);elsereturn false;}public static void main(String[] args){BiTNode root1=constructTree(); //3.4节BiTNode root2=constructTree();boolean equal=isEqual(root1,root2);if(equal)System.out.println("这两棵树相等");elseSystem.out.println("这两棵树不相等");}}
程序的运行结果为
这两棵树相等算法性能分析：
这种方法对两棵树只进行了一次遍历，因此，时间复杂度为O(N)。此外，这种方法没有申请额外的存储空间。
感谢您的阅读，有任何问题欢迎评论区留言。