题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析：
首先，B=null,则返回false
如果B是A的子树，那么A中必然含有和B一模一样的子树
数的子结构示例
要找到A当中是否含有和B一样的结构的子树，那么可以分为两步走：
一、在A中找到和B的根节点值一样的节点R；
二、判断R节点下是否有和B一样结构的子树；
这是一个递归的过程。
递归的使用可以一下三步来完成求解过程：
1. 递归截止条件。
递归的截止条件是为了递归能够避免无限循环下去，首先来分析什么情况下递归截止返回遍历结果。
(1) 根据题目要求，如果B数是个空树，递归截止。
(2) 如果被遍历的树A是空树，自然而然递归截止。
(3) 如果比较的是B的尾节点，无法进行下去，递归也会截止。
(4) 如果A树从头遍历到尾始终没有和B的节点相同的节点，递归截止。
2. 递归的前后衔接。
如果A的根节点值以及左右子节点情况和B的根节点完全相同，那么A和B都继续滑动到他们的左右子节点进行比较；如果A的根节点值和B的根节点值是相同的，但是左右子节点的情况是不相同的，那么只滑动A到他的左右子节点再与B比较。如果A的根节点的值和B的根节点的值不相同，那么A直接滑动到他的左右自己点再和B的根节点比较，直到遍历完成。
3. 递归节点数据的处理。
根据题目，本题目中用到的递归并没有数据处理，只是比较判断两个树节点是否相同。对于其他递归，可以具体情况具体对待。
代码：
/**
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(root2 == null || root1 == null)
return false;
boolean result = false;
//A上的节点R和B的根节点相同，则判断下面的结构是否相同。
if(root1.val == root2.val)
result = isSubTree(root1,root2);
//如果上一步判断的结果是false，那么，将A往下遍历比较，先比较A的左子树中有没有和B相同的子结构
if(result == false)
result = HasSubtree(root1.left,root2);
//再比较A的右子树中有没有和B相同的子结构
if(result == false)
result = HasSubtree(root1.right,root2);
//递归遍历完了
return result;
}
//如果已经有节点R和B的根节点相同，那么用这个方法来判断R的子树和B的结构是否一致
private boolean isSubTree(TreeNode root1,TreeNode root2){
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root2.val != root1.val)
return false;
return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
}
}
后来看到大神的j简洁写法如下：
/**
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(root2 == null || root1 == null)
return false;
return isSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
//如果已经有节点R和B的根节点相同，那么用这个方法来判断R的子树和B的结构是否一致
private boolean isSubTree(TreeNode root1,TreeNode root2){
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root2.val != root1.val)
return false;
return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
}
}
运行结果
