AlgoPressAppearance
26-树的子结构
题目描述
https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
思路【错误】
判断各自节点，如果相等判断子树，这里有两个问题
- null 不属于任何子树，如果没有另外一个函数，这里的递归判断就会和题意冲突，因为递归结束的时候 TreeNode 肯定是 null，但是应该是属于某个子树的
- 当 A 和 B 相等的时候，就进入子树判断， 但是如果下面的情况，就会判断不正确，题目并没有说每个节点都不相同，当1相等的时候，走不到 else 环节了
1
/ \
3 5
/\ 判断 1
1 4 /
/ 2
2
参考代码【错误】
csharp
// 基本思路：
// 如果根节点相同，
// 则 1. 判断各自子节点，直到末尾 null，如果都相等都返回 true
// 2. 或者判断 左节点 和 右节点，因为可能从下面节点才开始相等
// 如果根节点不相等， 判断 B 是否和 A 的两个节点相等
private bool IsSubStructure(TreeNode A, TreeNode B){
if(A == null || B == null) {
return A == B;
}
if(A.val == B.val){ //相等判断子树
bool result = ( IsSubStructure1(A.left, B.left) || (A.left != null && B.left == null)) && (IsSubStructure1(A.right, B.right) || (A.right != null && B.right == null));
if(!result){
result = IsSubStructure1(A.left, B) || IsSubStructure1(A.right, B);
}
return result;
}
else{
return IsSubStructure1(A.left, B) || IsSubStructure1(A.right, B);
}
}
思路分析
只有一个函数的时候，判断会出错 B == null 的时候，不属于任何树的子树
但是 Match 的时候，是属于的 因为我们需要一个函数 IsMatch ，用来判断两棵树从当前节点开始完全包含，即每个节点都相等，然后最后节点都是 null，或者 A 非 null， B是 null了
这样判断子树的条件就是 IsMatch(A,B) 或者 IsSubStructure(A.left,B) 或者 IsSubStructure(A.right,B)
实现代码
csharp
public class Solution {
//只有一个函数的时候，判断会出错 B == null 的时候，不属于任何树的子树
//但是 Match 的时候，是属于的
// IsMatch 是判断两棵树完全相等，SubStructure 是判断包含的
public bool IsSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
return IsMatch(A,B) || IsSubStructure(A.left, B) || IsSubStructure(A.right, B);
}
private bool IsMatch(TreeNode A, TreeNode B){
if(A == null || B == null){
return A == B || A != null;
}
if(A.val != B.val){
return false;
}
return IsMatch(A.left, B.left) && IsMatch(A.right, B.right);
}
}
复习：20220611
csharp
public class Solution {
private bool HasSubTree(TreeNode A, TreeNode B){
if(A == null || B == null) {
if(B != null){
return false;
}
return true;
}
if(A.val == B.val){
return HasSubTree(A.left, B.left) && HasSubTree(A.right, B.right);
}
return false;
}
public bool IsSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
return HasSubTree(A,B) || IsSubStructure(A.left, B) || IsSubStructure(A.right, B);
}
}