C++刷剑指offer（面试题26. 树的子结构）【广度优先搜索】

糖逗

题目描述：

1. 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
   
2. 
   
3. B是A的子结构， 即 A中有出现和B相同的结构和节点值。
   
4. 
   
5. 例如:
   
6. 给定的树 A:
   
7. 
   
8.      3
   
9.     / \
   
10.    4   5
    
11.   / \
    
12.  1   2
    
13. 给定的树 B：
    
14. 
    
15.    4 
    
16.   /
    
17.  1
    
18. 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
    
19. 
    
20. 示例 1：
    
21. 
    
22. 输入：A = [1,2,3], B = [3,1]
    
23. 输出：false
    
24. 示例 2：
    
25. 
    
26. 输入：A = [3,4,5,1,2], B = [4,1]
    
27. 输出：true
    
28. 限制：
    
29. 
    
30. 0 <= 节点个数 <= 10000
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. using namespace std;
   
7. 
   
8. struct TreeNode{
   
9.         int val;
   
10.         TreeNode* left;
    
11.         TreeNode* right;
    
12.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
13.         }
    
14. };
    
15. 
    
16. TreeNode* CreateTree(vector<int> input){
    
17.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
18.         for(int i = 0; i < input.size(); i++){
    
19.                 res[i].val = input[i];
    
20.                 res[i].left = NULL;
    
21.                 res[i].right = NULL;
    
22.         }
    
23.         for(int i= 0; i < input.size(); i++){
    
24.                 if(2*i+1 < input.size()){
    
25.                         res[i].left = &res[2*i+1];
    
26.                 }
    
27.                 if(2*i+2 < input.size()){
    
28.                         res[i].right = &res[2*i+2];
    
29.                 }
    
30.                
    
31.         }
    
32.         return res;
    
33.         
    
34. }
    
35. 
    
36. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
37.     if(root == NULL) return;
    
38.     int insert = left + (right - left) / 2;
    
39.     res[depth][insert] = root->val;
    
40.            
    
41.     middle(root->left, res, left, insert - 1, depth + 1);
    
42.     middle(root->right, res, insert + 1, right, depth + 1);
    
43.     }
    
44. 
    
45. int treeDepth(TreeNode* root){
    
46.     if(root == NULL || root -> val == 0) return 0;
    
47.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
48. }
    
49.       
    
50. void PrintTree(TreeNode* root) {
    
51.     int depth = treeDepth(root);
    
52.     int width = pow(2, depth) - 1;
    
53.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
54.     middle(root, res, 0, width - 1, 0);
    
55.     for(int i = 0; i < res.size(); i++){
    
56.                 for(int j = 0; j < res[i].size();j++){
    
57.                         if(res[i][j] == 0){
    
58.                                 cout  << " ";
    
59.                         }
    
60.                         else{
    
61.                                 cout << res[i][j];
    
62.                         }
    
63.                        
    
64.                 }
    
65.                 cout << endl;
    
66.         }
    
67.         cout << "------------------" << endl;
    
68.     }
    
69. 
    
70. 
    
71. TreeNode* findNode(TreeNode* A, TreeNode* B){
    
72.         if(A == NULL) return A;
    
73.         queue <TreeNode*> temp;
    
74.         temp.push(A);
    
75.         while(!temp.empty()){
    
76.                 auto node = temp.front();
    
77.                 temp.pop();
    
78.                 if(node -> val == B -> val) return node;
    
79.                 if(node ->left != NULL) temp.push(node->left);
    
80.                 if(node -> right != NULL) temp.push(node -> right);
    
81.         }
    
82.         return NULL;
    
83. }
    
84. 
    
85. 
    
86. 
    
87. 
    
88. 
    
89. bool solution(TreeNode*A, TreeNode*B){
    
90.         if(A == NULL&& B!= NULL) return false;
    
91.     if(A != NULL && B == NULL) return true;
    
92.     if(A==NULL && B ==NULL) return true;
    
93.     if(A->val != B->val) return false;
    
94.     return solution(A->right,B->right) && solution(A->left, B->left);
    
95. }
    
96. 
    
97. bool isSubStructure(TreeNode*A, TreeNode*B){
    
98.     if(A!=NULL && B==NULL) return false;
    
99.     TreeNode* node = findNode(A, B);
    
100.     return solution(node, B);
     
101.    
     
102. }
     
103. 
     
104. int main(void){
     
105.         vector<int> input1, input2;
     
106.         cout << "send numbers for the first tree" << endl;
     
107.         int number1;
     
108.         while(cin >> number1){
     
109.                 input1.push_back(number1);
     
110.         }
     
111.         cin.clear();
     
112.         cout << "send numbers for the second tree" << endl;
     
113.         int number2;
     
114.         while(cin >> number2){
     
115.                 input2.push_back(number2);
     
116.         }
     
117.         
     
118.         TreeNode* root1 = CreateTree(input1);
     
119.         PrintTree(root1);
     
120.         
     
121.         TreeNode* root2 = CreateTree(input2);
     
122.         PrintTree(root2);
     
123.       
     
124.                 bool res =  isSubStructure(root1, root2);
     
125.                 cout << res << endl;
     
126.         return 0;
     
127. }
     

复制代码

注意事项：
1.解题思路：分两步，先找到A中包含B根节点的子节点，然后再递归比较A的子树C和B，判断B是否是C的子树。
2.第一步找子节点用到广度优先搜索。

糖逗

核心代码：

1. TreeNode* findNode(TreeNode* A, TreeNode* B){
   
2.         if(A == NULL) return A;
   
3.         queue <TreeNode*> temp;
   
4.         temp.push(A);
   
5.         while(!temp.empty()){
   
6.                 auto node = temp.front();
   
7.                 temp.pop();
   
8.                 if(node -> val == B -> val) return node;
   
9.                 if(node ->left != NULL) temp.push(node->left);
   
10.                 if(node -> right != NULL) temp.push(node -> right);
    
11.         }
    
12.         return NULL;
    
13. }
    
14. 
    
15. 
    
16. 
    
17. bool solution(TreeNode*A, TreeNode*B){
    
18.         if(A == NULL&& B!= NULL) return false;
    
19.     if(A != NULL && B == NULL) return true;
    
20.     if(A==NULL && B ==NULL) return true;
    
21.     if(A->val != B->val) return false;
    
22.     return solution(A->right,B->right) && solution(A->left, B->left);
    
23. }
    
24. 
    
25. bool isSubStructure(TreeNode*A, TreeNode*B){
    
26.     if(A!=NULL && B==NULL) return false;
    
27.     TreeNode* node = findNode(A, B);
    
28.     return solution(node, B);
    
29.    
    
30. }

复制代码

糖逗