每日一题 剑指offer（树的子结构）
每日一题 剑指offer（树的子结构）
小白学视觉
发布于 2019-10-24 00:53:04
发布于 2019-10-24 00:53:04
代码可运行
运行总次数：0
代码可运行
编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）
特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。
树的子结构
题目描述
输入两棵二叉树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};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2018-09-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
