题意
判断一棵树(参数二)是不是另一棵树(参数一)的子结构。
题解
递归第一棵树，找两棵树中值一样的节点。若找到后，用另一个函数判断以相同值得节点为根的树2是不是树1的子结构。
代码
class TreeNode{
double val;
TreeNode lChild;
TreeNode rChild;
TreeNode(double val){
this.val=val;
}
}
public class Main {
public static void main(String[] args) {
//test case
TreeNode node1=new TreeNode(1);
TreeNode node2=new TreeNode(2);
TreeNode node3=new TreeNode(3);
node1.lChild=node2;
node1.rChild=node3;
TreeNode node4=new TreeNode(4);
TreeNode node5=new TreeNode(1);
TreeNode node6=new TreeNode(2);
TreeNode node7=new TreeNode(3);
node4.lChild=node5;
node5.lChild=node6;
node5.rChild=node7;
if(hasSubTree(node4,node1)) {
System.out.print("true");
}
else {
System.out.print("false");
}
}
public static boolean hasSubTree(TreeNode root,TreeNode subTreeRoot) {
if(subTreeRoot==null) {
return true;
}
if(root==null) {
return false;
}
boolean ans=false;
if(equal(root.val,subTreeRoot.val)) {//根节点相同才开始判所在的两棵子树是否相同
ans=tree1HasTree2(root,subTreeRoot);
}
if(!ans) {//
ans=hasSubTree(root.lChild,subTreeRoot);
}
if(!ans) {
ans=hasSubTree(root.rChild,subTreeRoot);
}
return ans;
}
public static boolean tree1HasTree2(TreeNode root1,TreeNode root2) {
if(root2==null) {
return true;
}
if(root1==null) {
return false;
}
if(!equal(root1.val,root2.val)) {//递归过程中每次判断节点相同
return false;
}
return tree1HasTree2(root1.lChild,root2.lChild)&&tree1HasTree2(root1.rChild,root2.rChild);
}
public static boolean equal(double num1,double num2) {
return Math.abs(num1-num2)<0.0000001;
}
}