每日一题 剑指offer（树的子结构）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

树的子结构

题目描述

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

节点的定义为：

1struct TreeNode {
2        intval;
3        structTreeNode *left;
4        structTreeNode *right;
5        TreeNode(intx) :
6                         val(x),left(NULL), right(NULL) {
7        }
8};

解析

1.首先需要递归pRoot1树，找到与pRoot2根一样的节点，这需要一个遍历
2.找到相同的根节点后，要判断是否子树，仍需要一个一个遍历对比
我们之前已经做过很多和二叉树相关的题了，树的遍历我们一般就用递归来做，那么根据分析需要两个递归函数。

代码

1class Solution {
2public:
3    bool EqualSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
4    {
5        if(!pRoot2)
6            return true;
7        if(!pRoot1)
8            return false;
9        if (pRoot1->val == pRoot2->val)
10        {
11            return EqualSubTree(pRoot1->left, pRoot2->left) && EqualSubTree(pRoot1->right, pRoot2->right);
12        }
13        return false;
14    }
15    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
16    {
17        if (!pRoot2 || !pRoot1)
18            return false;
19        if (pRoot1->val == pRoot2->val)
20        {
21            if (EqualSubTree(pRoot1, pRoot2))
22                return true;
23        }
24        if (HasSubtree(pRoot1->left, pRoot2) )
25        {
26           return true;
27        }
28        if (HasSubtree(pRoot1->right, pRoot2))
29        {
30           return true;
31        }
32        return false;
33    }
34};