题目
- 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
- B是A的子结构， 即 A中有出现和B相同的结构和节点值。
示例
- 示例1
- 给定 A 树
3
/ \
4 5
/ \
1 2
- 给定 B 树
4
/
1
- 返回: true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
代码
- 边找边判断
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null)
return A == B;
if (A.val == B.val && dfs(A,B))
return true;
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
boolean dfs(TreeNode root,TreeNode B){
if (root == null || B == null)
return B == null;
return (root.val == B.val) && dfs(root.left, B.left) && dfs(root.right, B.right);
//注意 最后一句不是每个语句都要执行判断，当出现否的时候 直接跳出，& 则需要全部判断，&&不需要
}
}
代码分析： isSubStructure(TreeNode A, TreeNode B) 用来查找 B 的根节点是否出现在 A 中。dfs(TreeNode root,TreeNode B) 用来判断以 B 为根节点的这棵树是否与以 root 为根节点的这棵树相同。
注意：在代码 dfs 中，有可能 root 不为空，但是 B 为空，这种情况是允许存在的。
- 其他方法
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if(B == null) return true;
if(A == null || A.val != B.val) return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
思路：先序遍历树 A 中的每个节点 n；（对应函数 isSubStructure(A, B)）
判断树 A 中 以 n 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）
算法流程：
recur(A, B) 函数：
终止条件：
- 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
- 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
- 当节点 A 和 B 的值不同：说明匹配失败，返回 false ；
返回值：
- 判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
- 判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
isSubStructure(A, B) 函数：
特例处理：
- 当 树 A 为空 或 树 B 为空 时，直接返回 false ；
返回值：
- 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
- 以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
- 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
- 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；
- 其他方法
class Solution {
public:
bool isSub(TreeNode* p1, TreeNode* p2){
if(!p2) return true;
if(!p1 || p1->val != p2->val) return false;
return isSub(p1->left,p2->left) && isSub(p1->right,p2->right);
}
bool hasSubtree(TreeNode* p1, TreeNode* p2) {
if(!p1 || !p2) return false;
if(isSub(p1,p2)) return true;
return hasSubtree(p1->left,p2) || hasSubtree(p1->right,p2);
}
};
代码分析：2022/1/14 我又把这道题做了一遍，明明我觉得思路很清晰，但提交一直错误。后来发现：
if(isSub(p1,p2)) return true;
这句代码被我写成了：
if(p1->val == p2->val) return isSub(p1,p2);
我自认为这样写提高了效率，其实这相当于如果第一次比较不成功，就会直接返回 false，后面的的递归就走不到了。所以还是需要一个一个传进 isSub() 比较。
