题目

输入两颗二叉树A和B，判断B是否是A的子结构，例如下图中B是A的子结构

              A                                                        B

参考代码1

bool IsPartTree(TreeNode *root1, TreeNode *root2){     if(root1 == NULL && root2 == NULL || root1!= NULL && root2 == NULL)          return true;     else if (root1 == NULL && root2 != NULL)          return false;     else     {         if ((root1->val == root2->val) && IsPartTree(root1->left, root2->left) && IsPartTree(root1->right, root2->right))            return true;         else             return IsPartTree(root1->left, root2) || IsPartTree(root1->right, root2);     }}

测试

#include 
      
       #include 
       
        using namespace std;struct TreeNode{       int val;       TreeNode *left;       TreeNode *right;       TreeNode(int v) : val(v), left(NULL), right(NULL) {}};bool IsPartTree(TreeNode *root1, TreeNode *root2){     if(root1 == NULL && root2 == NULL || root1!= NULL && root2 == NULL)              return true;     else if (root1 == NULL && root2 != NULL)          return false;     else     {         if ((root1->val == root2->val) && IsPartTree(root1->left, root2->left) && IsPartTree(root1->right, root2->right))            return true;         else             return IsPartTree(root1->left, root2) || IsPartTree(root1->right, root2);     }}int main(){    TreeNode *root1 = new TreeNode(8);    TreeNode *p1 = new TreeNode(8);    TreeNode *p2 = new TreeNode(3);    TreeNode *p3 = new TreeNode(2);    TreeNode *p4 = new TreeNode(9);    TreeNode *p5 = new TreeNode(4);    TreeNode *root2 = new TreeNode(8);    TreeNode *p6 = new TreeNode(2);    TreeNode *p7 = new TreeNode(9);    root1->left = p1;    root1->right = p2;    p1->left = p3;    p1->right = p4;    p4->left = p5;    root2->left = p6;    root2->right = p7;    cout << "::" << IsPartTree(root1, root2) << endl;    cout << "::" << IsPartTree(p1, root2) << endl;    cout << "::" << IsPartTree(root2, p2) << endl;    cout << "::" << IsPartTree(p3, root2) << endl;    system("pause");}
       
      

 

参考代码2（参考《剑指offer》）

bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2){    bool result = false;    if(p1 != NULL && p2 != NULL)    {        if(p1->m_nValue == p2->m_nValue)            result = IsPart(p1, p2);        if(!result)            result = HasPartTree(p1->m_pLeft, p2);        if(!result)            result = HasPartTree(p1->m_pRight, p2);    }    return result;}

测试

#include 
      
       using namespace std;struct BinaryTreeNode{    int m_nValue;    BinaryTreeNode *m_pLeft;    BinaryTreeNode *m_pRight;};void CreateTree1(BinaryTreeNode *root){    BinaryTreeNode *p1 = new(BinaryTreeNode);    p1->m_nValue = 8;    p1->m_pLeft = NULL;    p1->m_pRight = NULL;    root->m_pLeft = p1;    BinaryTreeNode *p2 = new(BinaryTreeNode);    p2->m_nValue = 7;    p2->m_pLeft = NULL;    p2->m_pRight = NULL;    root->m_pRight = p2;    BinaryTreeNode *p3 = new(BinaryTreeNode);    p3->m_nValue = 9;    p3->m_pLeft = NULL;    p3->m_pRight = NULL;    p1->m_pLeft = p3;    BinaryTreeNode *p4 = new(BinaryTreeNode);    p4->m_nValue = 2;    p4->m_pLeft = NULL;    p4->m_pRight = NULL;    p1->m_pRight = p4;    BinaryTreeNode *p5 = new(BinaryTreeNode);    p5->m_nValue = 4;    p5->m_pLeft = NULL;    p5->m_pRight = NULL;    p4->m_pLeft = p5;    BinaryTreeNode *p6 = new(BinaryTreeNode);    p6->m_nValue = 7;    p6->m_pLeft = NULL;    p6->m_pRight = NULL;    p4->m_pRight = p6;}void CreateTree2(BinaryTreeNode *root){    BinaryTreeNode *p1 = new(BinaryTreeNode);    p1->m_nValue = 9;    p1->m_pLeft = NULL;    p1->m_pRight = NULL;    root->m_pLeft = p1;    BinaryTreeNode *p2 = new(BinaryTreeNode);    p2->m_nValue = 2;    p2->m_pLeft = NULL;    p2->m_pRight = NULL;    root->m_pRight = p2;}void MidTranverse(BinaryTreeNode *root){    if(root != NULL)    {        MidTranverse(root->m_pLeft);        cout << root->m_nValue << " ";        MidTranverse(root->m_pRight);    }}void DeleteTree(BinaryTreeNode *root){    if(root != NULL)    {        DeleteTree(root->m_pLeft);        DeleteTree(root->m_pRight);        delete(root);        root = NULL;    }}bool IsPart(BinaryTreeNode *p1, BinaryTreeNode *p2){    if(p2 == NULL)        return true;    else if(p1 == NULL)        return false;    else    {        if(p1->m_nValue != p2->m_nValue)            return false;        else if(IsPart(p1->m_pLeft, p2->m_pLeft) && IsPart(p1->m_pRight, p2->m_pRight))            return true;    }}bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2){    bool result = false;    if(p1 != NULL && p2 != NULL)    {        if(p1->m_nValue == p2->m_nValue)            result = IsPart(p1, p2);        if(!result)            result = HasPartTree(p1->m_pLeft, p2);        if(!result)            result = HasPartTree(p1->m_pRight, p2);    }    return result;}int main(){    BinaryTreeNode *tree_1 = new(BinaryTreeNode);    BinaryTreeNode *tree_2 = new(BinaryTreeNode);    tree_1->m_nValue = 8;    tree_1->m_pLeft = NULL;    tree_1->m_pRight = NULL;    tree_2->m_nValue = 8;    tree_2->m_pLeft = NULL;    tree_2->m_pRight = NULL;    CreateTree1(tree_1);    CreateTree2(tree_2);    cout << "Result:" << HasPartTree(tree_1->m_pRight, tree_2) << endl;    DeleteTree(tree_1);    DeleteTree(tree_2);}