剑指offer17：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

1 题目描述

　　输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

2 思路和方法

（1）先在A中找和B的根节点相同的结点

（2）找到之后遍历对应位置的其他结点，直到B中结点遍历完，都相同时，则B是A的子树

（3）对应位置的结点不相同时，退出继续在A中寻找和B的根节点相同的结点，重复步骤，直到有任何一棵二叉树为空退出

3 C++核心代码

3.1 递归实现1

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
13     {
14         //1.先找到和子树根节点相同的结点
15         bool flag=false;
16         if((pRoot1!=NULL)&&(pRoot2!=NULL))
17         {
18             if(pRoot1->val==pRoot2->val)
19                 //开始判断，此时找到了和子树根节点相同的结点
20                 flag=HasSubtreetty(pRoot1, pRoot2);
21 
22             if(!flag)
23 
24                 flag=HasSubtree(pRoot1->left, pRoot2);
25 
26             if(!flag)
27 
28                 flag=HasSubtree(pRoot1->right, pRoot2);
29         }
30         return flag;
31     }
32     
33     bool HasSubtreetty(TreeNode* pRoot1, TreeNode* pRoot2)
34     {
35         //该函数需要判断在找到和子树根节点相同的结点之后，判断其余结点是否相同
36         if(pRoot2==NULL)
37             return true;
38         if((pRoot1==NULL)&&(pRoot2!=NULL))
39             return false;
40         if(pRoot1->val!=pRoot2->val)
41             return false;
42         return HasSubtreetty(pRoot1->left, pRoot2->left)&&HasSubtreetty(pRoot1->right, pRoot2->right);
43     }
44 };

View Code

3.2 递归实现2

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     bool IsSubtree(TreeNode* p1, TreeNode* p2)
13     {
14         if(p2==NULL)return 1;
15         if(p1==NULL)return 0;
16 
17         if(p1->val != p2->val)return 0;
18 
19         return IsSubtree(p1->left,p2->left) && IsSubtree(p1->right,p2->right);
20     }
21     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
22     {
23         if(pRoot1==NULL || pRoot2==NULL)return 0;
24 
25         return IsSubtree(pRoot1,pRoot2)||
26             HasSubtree(pRoot1->left,pRoot2) ||
27             HasSubtree(pRoot1->right,pRoot2);
28     }
29 };

View Code

4 完整代码

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 
 6 //struct ListNode {
 7 //    int val;
 8 //    struct ListNode *next;
 9 //    ListNode(int x) : val(x), next(NULL) {}
10 //};
11 
12 struct TreeNode {
13     int val;
14     struct TreeNode *left;
15     struct TreeNode *right;
16     TreeNode(int x) :
17         val(x), left(NULL), right(NULL) {
18     }
19 };
20 
21 class Solution {
22 public:
23     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
24     {
25         //1.先找到和子树根节点相同的结点
26         bool flag = false;
27         if ((pRoot1 != NULL) && (pRoot2 != NULL))
28         {
29             if (pRoot1->val == pRoot2->val)
30                 //开始判断，此时找到了和子树根节点相同的结点
31                 flag = HasSubtreetty(pRoot1, pRoot2);
32 
33             if (!flag)
34 
35                 flag = HasSubtree(pRoot1->left, pRoot2);
36 
37             if (!flag)
38 
39                 flag = HasSubtree(pRoot1->right, pRoot2);
40         }
41         return flag;
42     }
43 
44     bool HasSubtreetty(TreeNode* pRoot1, TreeNode* pRoot2)
45     {
46         //该函数需要判断在找到和子树根节点相同的结点之后，判断其余结点是否相同
47         if (pRoot2 == NULL)
48             return true;
49         if ((pRoot1 == NULL) && (pRoot2 != NULL))
50             return false;
51         if (pRoot1->val != pRoot2->val)
52             return false;
53         return HasSubtreetty(pRoot1->left, pRoot2->left) && HasSubtreetty(pRoot1->right, pRoot2->right);
54     }
55 };
56 
57 int main()
58 {
59     Solution *s = new Solution();
60     TreeNode *t1 = new TreeNode(8);
61     TreeNode *t2 = new TreeNode(9);
62     TreeNode *t3 = new TreeNode(3);
63     TreeNode *t4 = new TreeNode(8);
64     TreeNode *t5 = new TreeNode(2);
65     TreeNode *t6 = new TreeNode(4);
66     TreeNode *t7 = new TreeNode(7);
67     TreeNode *t8 = new TreeNode(6);
68     TreeNode *t9 = new TreeNode(5);
69     t1->left = t2; t1->right = t3; 
70     t2->left = t4; t2->right = t5; t3->left = t6; t3->right = t7;
71     t4->left = t8; t4->right = t9;
72 
73     TreeNode *tt1 = new TreeNode(8);    //只有8 6相同时也是子树，返回值为1
74     //TreeNode *tt2 = new TreeNode(6);
75     //TreeNode *tt3 = new TreeNode(5);
76     TreeNode *tt2 = new TreeNode(1);
77     TreeNode *tt3 = new TreeNode(4);
78     tt1->left = tt2; tt1->right == tt3;
79 
80     bool out_tree = s->HasSubtree(t1, tt1);
81     cout << out_tree << endl;
82 
83     system("pause");
84     return 0;
85 }

View Code

参考资料

https://blog.csdn.net/weixin_36125166/article/details/75939373

https://blog.csdn.net/danxibaoxxx/article/details/93402407