1 /*************************************************************************  2     > File Name: 17_MirrorOfBinaryTree.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年08月30日 星期二 17时12分37秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <stdlib.h> 10 #include <malloc.h> 11 #include <bits/stdc++.h> 12  13 using namespace std; 14  15 // 二叉树结构体 16 struct TreeNode 17 { 18     int val; 19     TreeNode* left; 20     TreeNode* right; 21 }; 22  23 TreeNode* createTree() 24 { 25     TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); 26     root->val = 8; 27     root->left = (TreeNode*)malloc(sizeof(TreeNode)); 28     root->left->val = 8; 29     root->right = (TreeNode*)malloc(sizeof(TreeNode)); 30     root->right->val = 7; 31     root->right->left = NULL; 32     root->right->right = NULL; 33     root->left->left = (TreeNode*)malloc(sizeof(TreeNode)); 34     root->left->left->val = 9; 35     root->left->left->left = NULL; 36     root->left->left->right = NULL; 37     root->left->right = (TreeNode*)malloc(sizeof(TreeNode)); 38     root->left->right->val = 2; 39     root->left->right->left = (TreeNode*)malloc(sizeof(TreeNode)); 40     root->left->right->left->val = 4; 41     root->left->right->left->left = NULL; 42     root->left->right->left->right = NULL; 43     root->left->right->right = (TreeNode*)malloc(sizeof(TreeNode)); 44     root->left->right->right->val = 7; 45     root->left->right->right->left = NULL; 46     root->left->right->right->right = NULL; 47      48     return root; 49 } 50  51 TreeNode* createSubTree() 52 { 53     TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); 54     root->val = 8; 55     root->left = (TreeNode*)malloc(sizeof(TreeNode)); 56     root->left->val = 9; 57     root->right = (TreeNode*)malloc(sizeof(TreeNode)); 58     root->right->val = 2; 59     root->left->left = NULL; 60     root->left->right = NULL; 61     root->right->left = NULL; 62     root->right->right = NULL; 63      64     return root; 65 } 66  67 bool DoesTree1HaveTree2(TreeNode* root1, TreeNode* root2) 68 { 69     if (root2 == NULL) 70         return true; 71     if (root1 == NULL) 72         return false; 73     if (root1->val != root2->val) 74         return false; 75      76     return DoesTree1HaveTree2(root1->left, root2->left) && DoesTree1HaveTree2(root1->right, root2->right); 77 } 78  79 bool hasSubTree(TreeNode* root1, TreeNode* root2) 80 { 81     int ret = false; 82     if (root1!=NULL && root2!=NULL) 83     { 84         if (root1->val == root2->val) 85             ret = DoesTree1HaveTree2(root1, root2); 86         if (ret == false) 87             ret = hasSubTree(root1->left, root2); 88         if (ret == false) 89             ret = hasSubTree(root1->right, root2); 90     } 91 } 92  93 // 层序遍历二叉树 94 void PrintTreeByLevel(TreeNode* root) 95 { 96     if (root == NULL) 97         return; 98      99     vector<TreeNode*> vec;100     vec.push_back(root);101     int cur = 0;102     int last = 1;103     104     while (cur < vec.size())105     {106         last = vec.size();107         while (cur < last)108         {109             printf("%d ", vec[cur]->val);110             if (vec[cur]->left != NULL)111                 vec.push_back(vec[cur]->left);112             if (vec[cur]->right != NULL)113                 vec.push_back(vec[cur]->right);114             115             ++ cur;116         }117         printf("\n");118     }119 }120 121 int main()122 {123     TreeNode* tree1 = createTree();124     TreeNode* tree2 = createSubTree();125     126     PrintTreeByLevel(tree1);127     printf("\n");128     PrintTreeByLevel(tree2);129     printf("\n");130     131     bool ret = hasSubTree(tree1, tree2);132     if (ret == true)133         printf("Yes\n");134     else135         printf("No\n");136     137     return 0;138 }