vlambda博客
学习文章列表

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

猿媛之家

已推送大量原创内容

已出版:

C、java、python、go、php、js、kotlin、scala、c#

等各种语言的面试笔试知识点书籍


已在菜单栏开源持续更新分类整理,干货满满


三步加星,方便阅读


本题来源:百度面试题

难度指数:3     考察频率:4


题目描述:

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

分析与解答:

如果两棵二叉树root1root2相等,那么root1root2结点的值相同,同时它们的左右孩子也有着相同的结构,并且对应位置上结点的值相等,即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); else return 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("这两棵树相等"); else System.out.println("这两棵树不相等"); }}

程序的运行结果为

这两棵树相等

算法性能分析:

这种方法对两棵树只进行了一次遍历,因此,时间复杂度为O(N)。此外,这种方法没有申请额外的存储空间。



感谢您的阅读,有任何问题欢迎评论区留言