[LC]26. 树的子结构

🚩传送门：力扣题目

题目

输入两棵二叉树和，判断是不是的子结构。(约定空树不是任意一个树的子结构)
是的子结构， 即 中有出现和相同的结构和节点值。

例如下图所示就是一个子结构
，
示例 1：

输入：A = [1,2,3], B = [3,1] 输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1] 输出：true

解题思路：递归

若树是树的子结构，则子结构的根节点可能为树的任意一个节点。因此，判断树是否是树的子结构，需完成以下两步工作：

1. 先序遍历树中的每个节点 ；（对应函数 ）
2. 判断树 中以节点 的为根的子树中是否包含树

复杂度分析

时间复杂度：，其中 , 分别是树和树的节点数量

空间复杂度：， 当树和树都退化为链表时，递归调用深度最大。

我的代码

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null) return false;    // 约定空树不是任意一个树的子结构
        if (A == null) return false;    // B非空,A空一定不可能匹配
        // A为根的子结构 || A左子树中的子结构 || A右子树中的子结构
        return (isMatching(A, B)) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean isMatching(TreeNode A, TreeNode B) {
        // B 空匹配完成
        if (B == null) return true;
        // B 非空 A 空了说明不能匹配
        if (A == null) return false;
        // 均非空时,根值相等,且左右子树匹配
        return A.val == B.val && isMatching(A.left, B.left) && isMatching(A.right, B.right);
    }
}