- 浏览: 778477 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
萨琳娜啊:
Java读源码之Netty深入剖析网盘地址:https://p ...
Netty源码学习-FileRegion -
飞天奔月:
写得有趣 ^_^
那一年你定义了一个接口 -
GoldRoger:
第二个方法很好
java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 -
bylijinnan:
<script>alert("close ...
自己动手实现Java Validation -
paul920531:
39行有个bug:"int j=new Random ...
java-蓄水池抽样-要求从N个元素中随机的抽取k个元素,其中N无法确定
思路来自:http://zhedahht.blog.163.com/blog/static/25411174201011445550396/
tree1HaveAllNodesOfTree2这个方法是判断是否tree1包含了tree2的所有节点,如果tree2是空树,那就认为tree1包含了tree2,反之则不是
这方法是在递归里面调用的,会有一个时候出现tee1==null 或者tree2==null
import ljn.help.*; public class HasSubtree { /**Q50. * 输入两棵二叉树A和B,判断树B是不是A的子结构。 例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一样的,因此B就是A的子结构。 1 8 / \ / \ 8 7 9 2 / \ 9 2 / \ 4 7 */ public static void main(String[] args) { int[] data01={1,8,7,9,2,0,0,0,0,4,7}; Node tree01=Helper.createTree(data01); int[] data02={8,9,2}; Node tree02=Helper.createTree(data02); boolean result=hasSubtree(tree01,tree02); System.out.println(result);//true /* * hasSubtreeByOrder() does not work. * preOrder and inOrder can define a unique BTree,but * inOrderOfTree1=9,8,4,2,7,1,7 * inOrderOfTree2=9,8,2 */ result=hasSubtreeByOrder(tree01,tree02); System.out.println(result);//false } //hasSubtree():just some "boundary condition".see hasSubtreeCore(). public static boolean hasSubtree(Node tree1,Node tree2){ if((tree1==null&&tree2!=null)|| tree1!=null&&tree2==null){ return false; } if(tree1==null&&tree2==null){ return true; } return hasSubtreeCore(tree1,tree2); } public static boolean hasSubtreeCore(Node tree1,Node tree2){ boolean result=false; if(tree1.getData()==tree2.getData()){//if roots are equal,test if both leftTree and rightTree are equal result=tree1HaveAllNodesOfTree2(tree1,tree2); } //roots are not equal if(!result&&tree1.getLeft()!=null){//find tree2 in tree1's left child,if exists result=hasSubtreeCore(tree1.getLeft(),tree2); } if(!result&&tree1.getRight()!=null){//find tree2 in tree1's right child,if exists result=hasSubtreeCore(tree1.getRight(),tree2); } return result; } public static boolean tree1HaveAllNodesOfTree2(Node tree1,Node tree2){ if(tree2==null){ return true; } if(tree1==null){ return false; } if(tree1.getData()!=tree2.getData()){ return false; } //now the roots are equal.Test left tree and right tree return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&& tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight()); } public static boolean hasSubtreeByOrder(Node tree1,Node tree2){ StringBuilder sb=new StringBuilder(); preOrder(tree1,sb); String preOrderOfTree1=sb.toString(); sb.setLength(0); preOrder(tree2,sb); String preOrderOfTree2=sb.toString(); if(preOrderOfTree1.indexOf(preOrderOfTree2)==-1){ return false; } sb.setLength(0); inOrder(tree1,sb); String inOrderOfTree1=sb.toString(); sb.setLength(0); inOrder(tree2,sb); String inOrderOfTree2=sb.toString(); return inOrderOfTree1.indexOf(inOrderOfTree2)!=-1; } public static void preOrder(Node node,StringBuilder sb){ if(node==null){ return; } sb.append(node.getData()+","); preOrder(node.getLeft(),sb); preOrder(node.getRight(),sb); } public static void inOrder(Node node,StringBuilder sb){ if(node==null){ return; } inOrder(node.getLeft(),sb); sb.append(node.getData()+","); inOrder(node.getRight(),sb); } }
评论
2 楼
bylijinnan
2012-06-19
neyshule 写道
tree1HaveAllNodesOfTree2这个函数为什么这样写呢:
if(tree2==null){
return true;
}
if(tree1==null){
return false;
}
if(tree1.getData()!=tree2.getData()){
return false;
}
//now the roots are equal.Test left tree and right tree
return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
为什么tree2是null就是true?tree1是null是false?
if(tree2==null){
return true;
}
if(tree1==null){
return false;
}
if(tree1.getData()!=tree2.getData()){
return false;
}
//now the roots are equal.Test left tree and right tree
return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
为什么tree2是null就是true?tree1是null是false?
tree1HaveAllNodesOfTree2这个方法是判断是否tree1包含了tree2的所有节点,如果tree2是空树,那就认为tree1包含了tree2,反之则不是
这方法是在递归里面调用的,会有一个时候出现tee1==null 或者tree2==null
1 楼
neyshule
2012-06-19
tree1HaveAllNodesOfTree2这个函数为什么这样写呢:
if(tree2==null){
return true;
}
if(tree1==null){
return false;
}
if(tree1.getData()!=tree2.getData()){
return false;
}
//now the roots are equal.Test left tree and right tree
return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
为什么tree2是null就是true?tree1是null是false?
if(tree2==null){
return true;
}
if(tree1==null){
return false;
}
if(tree1.getData()!=tree2.getData()){
return false;
}
//now the roots are equal.Test left tree and right tree
return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
为什么tree2是null就是true?tree1是null是false?
发表评论
-
百度笔试题:一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序
2012-12-21 18:17 4051import java.util.Arrays; ... -
java-56-动态规划-最长公共子序列
2012-03-12 00:14 2931http://zhedahht.blog.163.com/bl ... -
java-60-在O(1)时间删除链表结点
2012-03-12 00:12 1960public class DeleteNode_O1_ ... -
java-57-用两个栈实现队列&&用两个队列实现一个栈
2012-03-11 11:25 10755import java.util.ArrayList; ... -
java-26-左旋转字符串
2012-03-11 11:23 3050public class LeftRotateString ... -
java-66-用递归颠倒一个栈。例如输入栈{1,2,3,4,5},1在栈顶。颠倒之后的栈为{5,4,3,2,1},5处在栈顶
2012-03-08 20:41 4949import java.util.Stack; pu ... -
java-54- 调整数组顺序使奇数位于偶数前面
2012-03-06 21:09 3663import java.util.Arrays; imp ... -
java-63-在字符串中删除特定的字符
2012-03-05 16:47 2295public class DeleteSpecific ... -
java-67-扑克牌的顺子.从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的.2-10为数字本身,A为1,J为11,Q为12,K为13,而大
2012-03-05 15:46 6205package com.ljn.base; import ... -
java-68-把数组排成最小的数。一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的。例如输入数组{32, 321},则输出32132
2012-03-05 10:38 6155import java.util.Arrays; imp ... -
java-69-旋转数组的最小元素。把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素
2012-02-29 10:30 3505public class MinOfShiftedAr ... -
java-67- n个骰子的点数。 把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。
2012-02-28 00:00 6394public class ProbabilityOfD ... -
java-71-数值的整数次方.实现函数double Power(double base, int exponent),求base的exponent次方
2012-02-27 21:43 3006public class Power { /* ... -
java-73-输入一个字符串,输出该字符串中对称的子字符串的最大长度
2012-02-27 16:14 5787public class LongestSymmtri ... -
java-75-二叉树两结点的最低共同父结点
2012-02-27 11:27 1519import java.util.LinkedList; ... -
java-74-数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字
2012-02-11 10:56 2470public class OcuppyMoreThan ... -
java-17-在一个字符串中找到第一个只出现一次的字符
2012-02-11 10:04 5837public class FirstShowOnlyO ... -
java-51-输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
2012-02-10 10:55 4245public class PrintMatrixClo ... -
java-61-在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差. 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5,
2012-02-09 23:08 2187思路来自:http://zhedahht. ... -
java-37.有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符串可以联接
2012-01-27 22:46 2298public class MaxCatenate { ...
相关推荐
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
1.Java有那些基本数据类型,String是不是基本数据类型,他们有何区别。 2.字符串的操作: 写一个方法,实现字符串的反转,如:输入abc,输出cba 写一个方法,实现字符串的替换,如:输入bbbwlirbbb,输出...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
A、直接法和间接法 B、直接法和替代法 C、直接法和迭代法 D、间接法和迭代法 参考答案:C 22春"计算机科学与技术"专业《计算方法》在线作业含答案参考10全文共4页,当前为第2页。 12. 非线性结构的逻辑特征是一个...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 73 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 78 7、写一个Singleton出来。 81 8、递归算法题1 84 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、...
1. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立的数据库系统称为网状数据库系统,其典型代表是DBTG...
IvorHorton还著有关于C、C++和Java的多部入门级好书,如《C语言入门经典(第4版)》和《C++入门经典(第3版)》。 译者 杨浩,知名译者,大学讲师,从事机械和计算机方面的教学和研究多年,发表论文数篇,参编和翻译的...
37、下面这条语句一共创建了多少个对象:String s="a"+"b"+"c"+"d"; .................. 25 38、try {}里有一个 return 语句,那么紧跟在这个 try 后的 finally {}里的 code 会不 会被执行,什么时候被执行,在 ...