树的子结构
考点：二叉树
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
代码格式
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
}
}
解题一
1.思路
要查找树A中是否存在和树B结构一样的子树，分成两步：
第一，在树A中找到和B的根结点的值一样的结点R；
第二，判断树A中以R为根结点的子树是不是包含和树B一样的结构。
判断树A中以R为根结点的子树是不是和树B具有相同的结构：
递归方法。
如果结点R的值和树B的根结点不相同，则以R为根结点的子树和树B肯定不具有相同的结点；如果它们的值相同，则递归地判断它们各自的左右结点的值是不是相同。递归终止的条件是我们遍历完了树A或者树B的叶结点。
如图：A中有一部分子树的结构和B是一样的，因此B是A的子结构。
image.png
(1)首先在树A中找树B的根节点8；
(2)判断树A中以8为根节点的子树8-9-2是不是和树B的一样。
2.代码如下：
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
//第一步：深度遍历
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null){
return false;
}
//如果找到与子树相同根的值，走判断方法
if(root1.val == root2.val){
if(judge(root1,root2)){
return true;
}
}
//遍历左孩子，右孩子
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
//第二步：判断是否相同
public boolean judge(TreeNode node1,TreeNode node2){
if(node2==null){ //如果树B只有一个根结点，则和树A匹配，返回正确
return true;
}
if(node1==null){ //树A结点不能为空
return false;
}
if(node1.val==node2.val){
return judge(node1.left,node2.left)&&judge(node1.right,node2.right);
}else{
return false;
}
}
}
