题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
实现如下：
//分两步 //第一步：寻找与B树根节点val相等的A树节点。如果找到进入第二步，否则继续寻找，直到找完A树 //第二步：以找的节点作为A树子树的根节点，同时遍历两棵树，判断是否所有节点都相同 //特殊情况： //1.进行第二步时注意有可能存在B树大小等于A的子树、B树大小小于A的子树、B树大小大于A的子树 //2.注意对无效值的防御 //3.减少递归此数，及时判断return /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; */ class Solution { public: //第二步 bool Subtree(TreeNode* pRoot1, TreeNode* pRoot2) { if (pRoot1 == NULL && pRoot2 == NULL) return true;//B树大小等于A的子树 if (pRoot1 != NULL && pRoot2 == NULL) return true;//B树大小小于A的子树 if (pRoot1 == NULL && pRoot2 != NULL) return false;//B树大小大于A的子树 if (pRoot1->val == pRoot2->val)//如果val相等则进行进一步比较 return Subtree(pRoot1->left, pRoot2->left) && Subtree(pRoot1->right, pRoot2->right); else//否则直接return return false; } //第一步 bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //对空指针防御 if (pRoot1 == NULL || pRoot2 == NULL) return false; TreeNode *p1 = pRoot1; bool flag = false;//是否相等标志 if (p1->val == pRoot2->val)//若A树有节点val等于B树根节点val，进入第二步 { flag = Subtree(p1, pRoot2);//开始第二步递归调用 if (flag) return flag;//如果是子结构，直接return } //否则继续第一步 flag = HasSubtree(p1->left, pRoot2);//对左子树进行第一步 if (flag) return flag; flag = HasSubtree(p1->right, pRoot2);//对右子树进行第一步 if (flag) return flag; return flag; } };