一.题目描述:
1.基本描述:
给定两颗二叉树,判断两颗二叉树是否相等.
2.难度
入门
二.解题思路
1.题目分析
首先,先理解题目的需求.根据题目可知,入参为两颗二叉树的根节点TreeRoot,处理过程为判断两颗二叉树是否相等(判断依据为两颗二叉树的结构一致以及对应节点value值相等),返回参数为布尔类型(true或false);由上可知,该题目的核心在于如何去判断两颗树的结构是否一致(解决:当前节点都为非空或都为空,左节点都为非空或都为空,右节点都为非空或都为空)
2.解决方案
(1)递归
此方案优点为实现简单,缺点为执行效率慢.具体实现过程为:先判断当前节点是否为空以及值是否相等;再获取当前子节点的左节点,以左节点作为新的当前节点,再调用本身的方法进行像之前当前节点一样的处理;再获取当前子节点的右节点,以右节点作为新的当前节点,再调用本身的方法进行像之前当前节点一样的处理;只要过程发现值不同的或是一个为空另一个为非空的,最终返回false,如果最终跑完了这个过程,即为true.
(2)循环
此方案优点为执行效率快,缺点为耗费了额外的空间以及实现相对递归方案难了一些.具体实现过程为:分别为两颗二叉树创建两个栈,然后把根节点分别放进去,写一个循环;先把栈顶元素取出来,然后比较两个节点,然后再分别把当前节点的左节点和右节点存入栈中,重新执行循环体,这样就可以比较到对应的每个节点.只有处理过程发现比较不同,最终返回false和break即可.如果跑完了循环,再去比较两个栈是否都为空,如果有一个不为空,表明这两颗二叉树结构不同,返回false,如果都为空,即两颗二叉树相等,返回true
三.参考答案
1.递归
2.循环
四.总结
这个题目乍一看,觉得挺简单的,的确是入门题目.但是真正去编码实现时,又不会很顺利,说到底还是缺少练习.总的来说一句话,真正的编程能力是练出来的,不是看出来的,一定要坚持多练多反思多总结.