力扣对应题目链接：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;
    }
};