题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路：
前序遍历A树，寻找A树中和B树根节点相同的节点。
A. 若A树的节点和B树的根节点相同，则A，B两树同时以当前节点开始前序遍历，比较A，B树中节点是否相同，若不相同则退出当前的遍历，并返回当前结果。
B. 若A树的节点和B树的根节点不相同，或A中返回结果为false，继续遍历A树，查看是否还存在与B树根节点相同的节点
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
bool isSameTree(TreeNode* x, TreeNode* y)
{
bool res = false;
if(y == NULL) return true;//y=NULL，证明B树中所有节点已经比较完了，并且均与A树节点相同
if(x == NULL) return false;//B树节点还没有比较完，A树节点已经比较完了。
if(x->val == y->val)
{
res = isSameTree(x->left,y->left);
if(res)
{
res = isSameTree(x->right,y->right);
}
}
return res;
}
bool HasSubtree(TreeNode*x, TreeNode* y)
{
bool res = false;
if(x==NULL || y==NULL)
return false;
if(x->val == y->val)//在A树中找到与B树根节点相同的节点
{
res = isSameTree(x,y);
}
if(!res)//没有找到相同的节点或B树此时不是A树种以当前节点为根节点树的子树
res = HasSubtree(x->left,y);
if(!res)
res = HasSubtree(x->right,y);
return res;
}
};
