【一刷《剑指Offer》】面试题 18：树的子结构

力扣对应题目链接：LCR 143. 子结构判断 - 力扣（LeetCode）

牛客对应题目链接：树的子结构_牛客题霸_牛客网 (nowcoder.com)

核心考点：二叉树理解，二叉树遍历。 

---

一、《剑指Offer》对应内容

---

二、分析问题

二叉树都是递归定义的，所以递归操作是比较常见的做法。

首先明白：子结构怎么理解，可以理解成子结构是原树的子树（或者一部分）。也就是说，B 要是 A 的子结构，那么 B 的根节点+左子树+右子树都得在 A 中存在且构成树形结构。

比较的过程要分为两步：

1. 先确定比较的起始位置。
2. 在确定从该位置开始，在比较其左右子树的内容是否一致。

---

三、代码

//力扣AC代码
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool hasSubtree(TreeNode* a, TreeNode* b){if(b==NULL) return true;if(a==NULL) return false;if(a->val!=b->val) return false;return hasSubtree(a->left, b->left) && hasSubtree(a->right, b->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {if(A==NULL || B==NULL) return false;bool result=false;if(A->val==B->val)result=hasSubtree(A, B);if(!result)result=isSubStructure(A->left, B);if(!result)result=isSubStructure(A->right, B);return result;}
};//牛客AC代码
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool isSubStructure(TreeNode* a, TreeNode* b){if(b==nullptr) return true;if(a==nullptr) return false;if(a->val!=b->val) return false;return isSubStructure(a->left, b->left) && isSubStructure(a->right, b->right);}bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if(pRoot1==nullptr || pRoot2==nullptr) return false;bool result=false;if(pRoot1->val==pRoot2->val)result=isSubStructure(pRoot1, pRoot2);if(!result)result=HasSubtree(pRoot1->left, pRoot2);if(!result)result=HasSubtree(pRoot1->right, pRoot2);return result;}
};