题目
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析
（1）在tree1中寻找tree2的根节点，如果找到了，就接着往下匹配左右节点，如果没有找到，就直接返回false，表示匹配失败；
（2）加入tree1的某个节点和tree2的根节点相等，但是左右子树并不相同，并不能说明tree2就不是tree1的子结构，应该继续往下寻找；
如上图所示，根节点1相同，但是左右子树并不相同，此时并不能说tree2不是tree1的子机构，因为在tree1的左子树中包含tree2这个结构。
思想比较简答，但是这个题感觉考得是代码的完整性和健壮性，就是对边界的判断。
主要考虑：
一、在寻找相同的根节点时：
（1）两颗树为空，直接返回false；
（2）任意一棵树为空，直接返回false；
（3）两棵树都不为空：
3.1 节点值相等，则判断节点之外的子结构；
3.2 节点值不相等，那么用tree1的当前节点的左孩子与tree2的根节点匹配；
3.3 tree1的当前节点的左孩子与tree2的根节点值不相等，用tree1的当前节点的右孩子与tree2的根节点匹配。
二、判断tree2是不是tree1的子结构 （1）tree1为空，tree2不为空，直接返回false，因为tree1的树的结构是大于等于tree2的；
（2）如果tree2为空，说明递归完成，之前的匹配都成功，直接返回true
（3）节点的值不相等，返回false。
代码
/**
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) {
boolean result = false;
// 匹配tree2的根节点
if (root1 != null && root2 != null) {
if (root1.val == root2.val) {
result = DoseTree1haveTree2(root1, root2);
}
if (result == false) {
result = HasSubtree(root1.left, root2);
}
if (result == false) {
result = HasSubtree(root1.right, root2);
}
}
return result;
}
private boolean DoseTree1haveTree2(TreeNode tree1,TreeNode tree2) {
// 如果树1为空，数2不为空，返回false，因为数2不可能大于数1
if (tree1 == null && tree2 != null) {
return false;
}
// 比较到tree2的节点为空，说明已经遍历完可tree2，并且匹配成功
if (tree2 == null) {
return true;
}
// 如果节点值不同，返回false
if (tree1.val != tree2.val) {
return false;
}
// 当前节点值相同，继续比较左右子树
return DoseTree1haveTree2(tree1.left, tree2.left) && DoseTree1haveTree2(tree1.right, tree2.right);
}
}
