题目描述
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/
4 5
/
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例：
输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
说明：
- 0 <= 节点个数 <= 10000
题目链接： https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
思路1
我们要判断 B 是否在 A 中，所以我们可以逐个判断以 A 中每个节点为根的树是否包含 B。方法是先获取 A 中的所有节点，然后遍历这些节点，判断以当前节点为根的树是否包含 B。获取 A 中所有节点可以使用 BFS 或者 DFS，这里使用 BFS。代码如下：
/**
* 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 isSubStructure(TreeNode* A, TreeNode* B) {
if(B==nullptr) return false;
vector<TreeNode*> nodes; // 保存 A 的所有节点
queue<TreeNode*> q;
q.push(A);
while(!q.empty()){
TreeNode* node = q.front(); q.pop();
nodes.push_back(node);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
for(auto node:nodes){
if(node->val==B->val){
if(judge(node, B)) return true; // 判断以node为根的树是否包含B
}
}
return false;
}
bool judge(TreeNode* A, TreeNode* B){
if(A==nullptr && B!=nullptr) return false;
if(A!=nullptr && B==nullptr) return true; // 注意这里返回true，例子A=[3,4,5,1,2], B=[4,1]
if(A==nullptr && B==nullptr) return true;
if(A->val==B->val){
return judge(A->left, B->left) && judge(A->right, B->right);
}else return false;
}
};
需要注意的是，judge 函数中的第 2 个判断条件 if(A!=nullptr && B==nullptr) 返回 true。而另一棵树的子树这一题是返回 false 的。
简化：
可以边 bfs 边判断，不需要用 nodes 数组存储节点后再判断。代码如下：
/**
* 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 isSubStructure(TreeNode* A, TreeNode* B) {
if(B==nullptr) return false;
queue<TreeNode*> q;
q.push(A);
while(!q.empty()){
TreeNode* node = q.front(); q.pop();
if(node->val==B->val){
if(judge(node, B)) return true; // 判断以node为根的树是否包含B
}
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
return false;
}
bool judge(TreeNode* A, TreeNode* B){
if(A==nullptr && B!=nullptr) return false;
if(A!=nullptr && B==nullptr) return true; // 注意这里返回true，例子A=[3,4,5,1,2], B=[4,1]
if(A==nullptr && B==nullptr) return true;
if(A->val==B->val){
return judge(A->left, B->left) && judge(A->right, B->right);
}else return false;
}
};
思路2
我们可以边对 A 中的节点进行递归边判断 B 是否在以 A 当前节点为根的树中。代码如下：
/**
* 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 isSubStructure(TreeNode* A, TreeNode* B) {
// 约定空树不是任意一个树的子结构
if(A==nullptr || B==nullptr) return false;
return isSame(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool isSame(TreeNode* A, TreeNode* B){
if(A==nullptr && B!=nullptr) return false;
if(A!=nullptr && B==nullptr) return true;
if(A==nullptr && B==nullptr) return true;
if(A->val==B->val){
return isSame(A->left, B->left) && isSame(A->right, B->right);
}else return false;
}
};