245. Subtree【LintCode java】
2024-09-03 12:04:33
Description
You have two very large binary trees: T1
, with millions of nodes, and T2
, with hundreds of nodes. Create an algorithm to decide if T2
is a subtree of T1
.
A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
Example
T2 is a subtree of T1 in the following case:
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
T2 isn't a subtree of T1 in the following case:
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
解题:判断一个二叉树是不是另一个二叉树的问题。思路还是很清晰的,但是有些细节还是要注意下的。两个递归,一个用来判断两个树是否完全一样,这个只要不一样就返回false。
还有一个递归函数是用来返回最终结果的。区别在于,如果第二个函数判断不等,还有继续往T2的子树探索,知道找到一个与T1完全相等的,或者一直到最后也不存在这样的函数。
比较容易错的是,在判断结点值的时候,要先判断结点是不是null(判空)。
代码如下:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
* @param T1: The roots of binary tree T1.
* @param T2: The roots of binary tree T2.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean equal(TreeNode T1, TreeNode T2){
if(T1 == null && T2 == null){
return true;
}else if(T1 == null && T2 != null || T1 != null && T2 == null||T1.val != T2.val){
return false;
}else{
return equal(T1.left, T2.left) && equal(T1.right, T2.right);
}
}
public boolean isSubtree(TreeNode T1, TreeNode T2) {
// write your code here
if(T2 == null)
return true;
if(T1 == null)
return false;
if(equal(T1 , T2))
return true;
else return isSubtree(T1.left, T2)||isSubtree(T1.right, T2);
}
}
最新文章
- SharePoint 2013 扩展查阅项功能
- javascript数组的一些方法实例
- Android通过URL加载网络图片
- 安装DirectX SDK (June 2010) 失败(Error Code S1023)(转)
- Java 碰撞的球 MovingBall (整理)
- PHP输入流php://input [转]
- mfc EDIT字体颜色
- Spring MVC JSON 实现JsonSerializer Date类型转换
- SQL Server分页查询方法整理
- 搭建php环境的几种方法
- javascript将base64编码的图片数据转换为file并提交
- 2-java-写代码技巧和交题注意点
- 在Eclipse下搭建Hibernate框架(加载hibernate工具插件,离线)
- Django积木块一——验证码
- Hyper-V虚拟机上安装一个图形界面的Linux系统
- Gym .101933 Nordic Collegiate Programming Contest (NCPC 2018) (寒假gym自训第四场)
- IO知识点整理(序列化,管道流,数据流,字节数组流,与编码)
- Hibernate学习笔记三:常用数据库操作语句
- SQL Server 属性不匹配。存在属性(Directory, Archive),包括属性(0),不包括属性(Archive, Compressed, Encrypted)
- Angularjs Directive - Compile vs. Link