这个题做出来了
第一想法是,B树的root节点值非常重要,先要找到A树和B.root值一样的节点,才能进行下面的判断。
所以先把找到节点后,再找结构的函数写出来:
public boolean test(TreeNode A,TreeNode B) { if(A==null) {return false;} //A可能为null,又因为B为null的结果全部排除了,所以直接返回错误 if(A.val!=B.val) {return false;} if(B.left!=null) { if(test(A.left,B.left)==false) {return false;} } if(B.right!=null) { if(test(A.right,B.right)==false) {return false;} } return true; }
下一步是怎么找root这个节点:
递归的条件是
A不含B子结构===test(A,B)为false&test(A.left,B)为false&test(A.right,B)为false
可能需要&&?
public boolean isSubStructure(TreeNode A, TreeNode B) { if(A==null||B==null) {return false;} //递归遍历这个树,如果找到节点符合的,test,如果不符合就下一个 if(!test(A,B)&&!isSubStructure(A.left,B)&&!isSubStructure(A.right,B)) { return false; } else {return true;} }