思路分析
定义：父树包含子树的所有节点，注意，空树不是任何数的子树。
父树：A
子树：B
解法：用递归来实现
- 从A树的根节点开始，判断其所有的节点是不是依次和树B相同；
- 如不同，递归调用函数，继续判断树A当前节点的左子树的所有节点或右子树的所有节点是否和树B所有节点相同，直到遍历到父树A的叶子节点；
- 如果不是完全相同，则树B不是树A子树；
- 如果直到遍历到树B的叶子节点，其所有节点在树A中均有，则树B是树A的子树。
代码实现
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null){
return false;
}
return isSubtree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
public boolean isSubtree(TreeNode root1,TreeNode root2){
if(root2==null){
return true;
}
if(root1==null){
return false;
}
if(root1.val==root2.val){
return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
}
return false;
}
}
