剑指offer 树的子结构

题目描述

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

题目思路：

可以分两步：

1）先找到A中和B根节点的值相等的节点R

2）判断树A中以R为根节点的子树是否包含和树B一样的结构。

特别注意：要访问地址的时候，一定要考虑为NULL的时候该怎么处理。

 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 private:
12     bool Equal(double num1, double num2) {
13         double subtract = num1 - num2;
14         return (subtract > -1e-8 && subtract < 1e-8);
15     }
16     bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2) {
17         //考虑是否先判断pRoot1 == NULL ?
18         //不能先简单判断pRoot1 == NULL就返回false, 因为可能pRoot2也为NULL,这是true
19         if (pRoot2 == NULL)
20             return true;
21         if (pRoot1 == NULL)
22             return false;
23         if (!Equal(pRoot1->val, pRoot2->val))
24             return false;
25         return DoesTree1HasTree2(pRoot1->left, pRoot2->left) && DoesTree1HasTree2(pRoot1->right, pRoot2->right);
26     }
27 public:
28     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
29     {
30         bool flag = false;
31         if (pRoot1 != NULL && pRoot2 != NULL) {
32             if (Equal(pRoot1->val, pRoot2->val)) {
33                 flag = DoesTree1HasTree2(pRoot1, pRoot2);
34             }
35             if (!flag) {
36                 flag = HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
37             }
38         }
39         return flag;
40     }
41 };