宁永久会员 2023年3月13日上午10:11

注意判断相等用两个等号

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //比对节点值是否一致
        if(A == null || B == null){
            return false;
        }
        if(A.val == B.val){
            if(recur(A, B)){
                return true;
            }
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    //节点数值一致后再一一比对。
    public boolean recur(TreeNode a, TreeNode b){
        if(b == null){
            return true;
        }
        if(a == null){
            return false;
        }
        if(a.val != b.val){
            return false;
        }
        return recur(a.left, b.left) && recur(a.right, b.right);
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月3日下午3:42

O(N^2) DFS 递归判断·

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        if (A.val == B.val && check(A, B)) return true;

        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean check(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null) return false;

        return A.val == B.val && check(A.left, B.left) && check(A.right, B.right);
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月20日下午6:26

#首先判断B是否是以A为根节点的子树，如果是子树，那B一定是A的子结构，如果不是子树，递归判断B是否是A左右子树的子结构

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if A == None or B == None:
            return False
        if self.isSubTree(A,B):
            return True
        if self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B):
            return True
        return False


    # 判断Tb是否是以Ta为根结点的子树
    def isSubTree(self,Ta,Tb):
        if Tb == None:
            return True

        if Ta == None:
            return False

        if Ta.val != Tb.val:
            return False
        return self.isSubTree(Ta.left,Tb.left) and self.isSubTree(Ta.right,Tb.right)

0 赞同 0 条回复

如梦似歌普通 2022年12月15日下午9:39

class Solution {
    /**
     *思路: 判断树B是否是树A的子结构，需要完成以下两步工作
     * 1.先序遍历树A中的每个结点n
     * 2.判断树A中以n为根结点的子树是否包含树B
     * 复杂度分析:
     * 时间复杂度: T(n) = O(mn),其中m,n分别为树A和树B的结点数量，先序遍历树A占用O(m),每次调用判断函数占用O(n)
     * 空间复杂度: S(n) = O(m),当树A和S树B都退化为链表时，递归调用深度最大。当m<=n时，遍历树与递归判断的总深度为m，当m>=n时，最差情况为遍历树A叶子结点，此时总递归深度为m。
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;  //因为空树不是任意一个树的子结构，所以如果A，B中有一棵空树的话则A/B一定不是对方的子结构，返回false
        }
        /**
         * 若B是A的子结构，则必须满足以下三种情况之一，因此用||连接
         * 1.以A为根结点的子树包含树B
         * 2.A的左子树包含树B
         * 3.A的右子树包含树B
         */
        //否则如果A和B都不为空，那么先序遍历A中每一个结点，只要A中任一一个结点包含B就返回true
        return contains(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    //判断以A为根的树是否包含B
    public boolean contains(TreeNode A, TreeNode B){
        //当结点B为空，说明树B已匹配完成，因此返回true
        if(B == null)
            return true;
        //当结点A为空，说明已经越过树A的叶子结点，即匹配失败，返回false
        //当结点A和结点B的值不同,说明匹配失败，返回false
        if(A == null || A.val != B.val)
            return false;
        //判断A和B的左右子树结点值是否相等
        return contains(A.left,B.left) && contains(A.right,B.right);
    }
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日上午10:52

class Solution {
public:
    bool iscontain(TreeNode* A, TreeNode* B){ //判断是否被包含
        if(B==nullptr) return true;
        if(A==nullptr) return false;
        if(A->val==B->val) return iscontain(A->left,B->left) && iscontain(A->right,B->right);
        else return false;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr) return false;
        if((A->val==B->val) && iscontain(A,B)) return true;
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

0 赞同 0 条回复

cute. 普通 2022年11月18日下午9:38

var isSubStructure = function(A, B) {
    if(A == null || B == null) {
        return false;
    }
    // 是否以A为根节点的子树
    if(isSubTree(A, B)) {
        return true;
    }
    // 递归判断
    if(isSubStructure(A.left, B) || isSubStructure(A.right, B)) {
        return true;
    }
    return false;

}
// 递归
var isSubTree = function(Ta, Tb) {
        // 递归结束条件
        // Tb的节点是不是检查完了
        if(Tb == null) {
            return true;
        }
        // Ta没有子节点，而Tb还有子节点，说明匹配不成功
        if(Ta == null) {
            return false;
        }
        if(Ta.val != Tb.val) {
            return false;
        }
        return isSubTree(Ta.left, Tb.left) && isSubTree(Ta.right, Tb.right);
    }

● 复杂度: O(n*m)【n为树A的节点，m为树B的节点个数】先序遍历树 A 占用 O(n) ，每次调用 isSubTree判断占用 O(m)
● 空间复杂度: o(h）【h为树A的高度】

0 赞同 0 条回复

xye 普通 2022年11月12日下午9:08

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if B == nil || A == nil {
        return false
    }
    return recur(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func recur(A, B *TreeNode) bool {
    if B == nil {
        return true
    }
    if A == nil || A.Val != B.Val {
        return false
    }
    return recur(A.Left, B.Left) && recur(A.Right, B.Right)
}

时间复杂度 O(MN) 空间复杂度树A的高度（递归的层数）

0 赞同 0 条回复

symbol 普通 2022年11月8日上午10:01

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil{
        return false
    }
    if Help(A, B){
        return true
    }
    return isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func Help(A *TreeNode, B *TreeNode) bool {
    // B空了
    if B == nil{
        return true
    }
    if A == nil || A.Val != B.Val {//A空了 或者A的值与B不相等了
        return false
    }
    //A的左子树 B的左子树继续递归
    isLeft := Help(A.Left, B.Left)
    //A的右子树 B的右子树继续递归
    isRight := Help(A.Right, B.Right)
    return isLeft && isRight
}

时间复杂度 O(MN) ：其中 M,N 分别为树 A 和树 B的节点数量；先序遍历树 A 占用 O(M) ，每次调用 recur(A, B) 判断占用 O(N) 。
空间复杂度 O(M) ：当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M ≤N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。

0 赞同 0 条回复

Asphyxia 普通 2022年11月6日下午5:11

需要写两个递归函数

/**
 * 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 isequal(TreeNode* A,TreeNode* B){
        if(!B){
            return true;
        }
        if(!A||A->val!=B->val){
            return false;
        }
        return isequal(A->left,B->left)&&isequal(A->right,B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A||!B){
            return false;
        }
        if(A->val==B->val){
            if(isequal(A,B)){
                return true;
            }
        }
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

0 赞同 0 条回复

刺猬普通 2022年11月5日下午12:02

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr || B == nullptr)
            return false;
        if(A->val == B->val && iscontain(A, B))
            return true;
        else
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool iscontain(TreeNode* A, TreeNode* B) {
        if(!B)
            return true;
        if(!A)
            return false;
        if(A->val == B->val)
            return iscontain(A->left, B->left) && iscontain(A->right, B->right);
        else 
            return false;
    }
};

时间复杂度：O(N*M)
空间复杂度：O(H) H为树A的高度

0 赞同 0 条回复

星河普通 2022年11月3日下午10:24

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);
    }
}
时间O(MN)空间O(N)

0 赞同 0 条回复

一只骆驼普通 2022年11月2日下午7:40

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        //三种情况，相等，是左、右子树的子树
        return helper(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
     //判断两棵树是不是相等
    public boolean helper(TreeNode A,TreeNode B){
        if(B==null) return true;
        if(A==null) return false;
        return A.val==B.val&&helper(A.left,B.left)&&helper(A.right,B.right);
    }
}

0 赞同 0 条回复

cxxz 普通 2022年11月1日下午11:37

感觉是两层递归，一层递归判断两树是否包含，一层递归遍历A树。

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL)
            return false;
        if (isSubTree(A, B))
            return true;
        if (isSubStructure(A->left, B) || isSubStructure(A->right, B))
            return true;
        return false;
    }

    //  判断A，B是否相等
    bool isSubTree(TreeNode* A, TreeNode* B) {
        if (B == NULL)      // B 遍历完了没返回 false，证明都匹配上了
            return true;
        if (A == NULL)       // A 遍历完了没返回,证明没匹配完，返回 false
            return false;
        if (A->val != B->val)
            return false;
        return (isSubTree(A->left, B->left) && isSubTree(A->right, B->right));
    }
};

时间复杂度O(M*N)，最差的情况是A的每个节点都和B的头节点相等，全部遍历
空间复杂度O(M+N)

0 赞同 0 条回复

lobort 普通 2022年11月1日下午9:37

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
//特殊情况
        if(A == null || B == null ){
            return false;
        }
        return fun(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);


    }
//定义fun函数 ：比较两个二叉树是否相同
    public boolean fun(TreeNode head1 , TreeNode head2){
//返回条件
        if(head2 == null){
            return true;
        }
        if(head1 == null){
            return false;
        }
//递归进行判断
        return head1.val == head2.val && fun(head1.right,head2.right) && fun(head1.left,head2.left);
    }
}

时间复杂度O(N) 空间复杂度O（m+n）两个二叉树的空间大小

0 赞同 0 条回复

Error 普通 2022年11月1日下午9:32

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:

        def recur(A, B):
            if not B:
                return True
            if not A or A.val != B.val:
                return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

时间复杂度 O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年11月1日下午2:27

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        //根节点相等，进行比较
        if(A.val == B.val && compare(A,B)){
            return true;
        }
        //根节点不相等，比较左子节点或右子节点
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    //逐个比较两棵树的节点
    public boolean compare(TreeNode A,TreeNode B){
        if(B == null){
            return true;
        }else if(A == null){
            return false;
        }
        if(A.val != B.val){
            return false;
        }
        return compare(A.left,B.left) && compare(A.right,B.right);
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年11月1日下午12:52

class Solution {

    bool contain(TreeNode *root1, TreeNode *root2) {
        if (!root2) return true;
        if (!root1) return false;
        if (root1->val != root2->val) return false;
        return contain(root1->left, root2->left) && contain(root1->right, root2->right);
    }
    bool issubstructure(TreeNode *root1, TreeNode *root2) {
        if (root1->val == root2->val && contain(root1, root2)) return true;
        return (root1->left ? issubstructure(root1->left, root2) : false) || (root1->right ? issubstructure(root1->right, root2) : false);
    }

public:
    bool isSubStructure(TreeNode *A, TreeNode *B) {
        if (!A || !B) return false;
        return issubstructure(A, B);
    }
};

空间复杂度：O(n)
时间复杂度：O(MN)

0 赞同 0 条回复

酥合普通 2022年10月31日下午11:17

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        if(isSubTree(A, B)){
            return true;
        }
        if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
            return true;
        }
        return false;
    }

    public boolean isSubTree(TreeNode p, TreeNode q){
        if(q == null){
            return true;
        }
        if(p == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSubTree(p.left, q.left) && isSubTree(p.right, q.right);
    }
}

时间复杂度 O(MN)：其中 M,NM,N 分别为树 A和树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 isSubTree判断占用 O(N)。
空间复杂度 O(n)

0 赞同 0 条回复

乱世枭雄普通 2022年10月31日下午10:03

思路：
先比头节点，根结点不同，递归找左右，结点找到相同头节点后；
对比树的结构是否相同，先比根结点是否相同，相同比左右子树是否相同

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null||B==null){
            return false;
        }

        if(isSubTree(A,B)){
            return true;
        }
        if (isSubStructure(A.left,B)||isSubStructure(A.right,B)){
            return true;
        }

        return false;


    }

    public boolean isSubTree(TreeNode A,TreeNode B){
        if(B == null){
            return true;
        }

        if(A == null){
            return false;
        }
        if(A.val!=B.val){
            return false;
        }

        return isSubTree(A.left,B.left)&&
               isSubTree(A.right,B.right);
    }
}

0 赞同 0 条回复

@ 普通 2022年10月31日下午4:29

时间复杂度 O(MN)：其中 M,NM,N 分别为树 AA 和树 BB 的节点数量；先序遍历树 AA 占用 O(M)O(M) ，每次调用 recur(A, B) 判断占用 O(N)O(N)。
空间复杂度 O(n)。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;

        if(isContain(A, B)) return true;

        if(isSubStructure(A.left, B) || isSubStructure(A.right, B))
            return true;

        return false;


    }

    public boolean isContain(TreeNode A, TreeNode B){
        if(B == null)
            return true;

        if(A == null)
            return false;

        if(A.val != B.val)
            return false;

        return isContain(A.left, B.left) && isContain(A.right, B.right);

    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午3:35

1.二叉树没有序
public boolean isSubStructure(TreeNode A , TreeNode B) {

        if (A == null || B == null) return false;

        if (isSubTree(A , B)) return true;

        if (isSubStructure(A.left , B) || isSubStructure(A.right , B)) return true;

        return false;
    }

    public boolean isSubTree(TreeNode Ta , TreeNode Tb) {
        if (Tb == null) return true;

        if (Ta == null) return false;

        if (Ta.val != Tb.val) return false;

        return isSubTree(Ta.left , Tb.left) && isSubTree(Ta.right , Tb.right);
    }

2.二叉树有序

    //这是有序结构的二叉树
    public boolean isSubStructure2(TreeNode A , TreeNode B) {
        //B是A的子结构，也就是说A中有出现和B相同的结构和节点值
        if (A == null && B == null) return true;
        if (A == null || B == null) return false;


        if (A.val == B.val) {
            return isSubStructure2(A.left , B.left) && isSubStructure2(A.right , B.right);
        } else if (A.val > B.val) {
            return isSubStructure2(A.left , B);
        } else return isSubStructure2(A.right , B);


    }

0 赞同 0 条回复

小肸永久会员 2022年10月31日下午2:34

思路：以树A中每一个节点为根节点形成一颗子树，看这个子树是否包含树B。
迭代法：时间复杂度O(MN)，空间复杂度取决于队列中的节点个数。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return true;
        }
        if (A == null || B == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(A);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (isSubStructureCore(node, B)) {
                return true;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return false;
    }
    private boolean isSubStructureCore(TreeNode A, TreeNode B) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(A);
        queue.add(B);
        boolean res = true;
        while (!queue.isEmpty()) {
            TreeNode a = queue.poll();
            TreeNode b = queue.poll();
            if (a.val != b.val) {
                res = (res && false);
            }
            if (b.left == null) {
                res = (res && true);
            } else {
                if (a.left == null) {
                    res = (res && false);
                } else {
                    queue.add(a.left);
                    queue.add(b.left);
                }         
            }
            if (b.right == null) {
                res = (res && true);
            } else {
                if (a.right == null) {
                    res = (res && false);
                } else {
                    queue.add(a.right);
                    queue.add(b.right);
                } 
            }
        }
        return res;
    }
}

递归法：时间复杂度O(MN)，空间复杂度O(M + N)。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;    
        }
        if (A == null && B == null) {
            return true;
        }
        return isSubStructureCore(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean isSubStructureCore(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        return A.val == B.val && isSubStructureCore(A.left, B.left) && isSubStructureCore(A.right, B.right);
    }

}

0 赞同 0 条回复

庄重普通 2022年10月31日下午2:17

class Solution {
public:
    // 函数功能:判断B是否为A的子结构
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL) return false;

        if(isSubTree(A,B)) return true;

        if(isSubStructure(A->left,B) || isSubStructure(A->right,B)) return true;

        return false;
    }
    // 函数功能：比对没一部分的子结构是否符合
    bool isSubTree(TreeNode* pA, TreeNode* pB){
        if(pB == NULL) return true;
        if(pA == NULL) return false;
        if(pA->val != pB->val) return false;

        return isSubTree(pA->left,pB->left) && isSubTree(pA->right,pB->right);
    }
};
//时间复杂度：O(nm) n为A的节点数 m为B的节点数
//空间复杂度：O(n)

0 赞同 0 条回复

绍熙普通 2022年10月31日下午1:26

思路：
1、先序遍历树 A 中的每个节点（n_A），对应函数 isSubStructure(A, B)。
2、判断树 A 中以节点n_A 为根节点的子树是否包含树 B ，对应函数 recur(A, 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);
    }
}

0 赞同 0 条回复

cxc 普通 2022年10月30日下午3:13

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recursion(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    public boolean recursion(TreeNode A, TreeNode B){
        if(B==null) return true;
        //当节点 AA 为空：说明已经越过树 AA 叶子节点，即匹配失败，返回 falsefalse ；
        if(A == null || A.val != B.val) return false;
        return recursion(A.left, B.left) && recursion(A.right, B.right);
    }
}

0 赞同 0 条回复

天然普通 2022年10月30日下午3:02

递归还是不会，感觉迭代好想一些时间复杂度O(mn),空间复杂度O(n)

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not (A and B): return False
        if A.val == B.val and self.find(A.left,B.left) and self.find(A.right,B.right):
           return True
        return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)


<pre><code>def find(self,root1,root2):
    if not root2:return True
    if not root1:return False
    if root1.val ==root2.val:
        return self.find(root1.left,root2.left) and self.find(root1.right,root2.right)
    else:return False
</code></pre>

0 赞同 0 条回复

wxc 普通 2022年10月30日上午10:34

啊

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

0 赞同 0 条回复

你有点可爱喔普通 2022年10月30日上午8:37

思路：需要定义一个函数判断B是否是A节点为根节点的一个子树，做递归进行判断
空间复杂度O(n)，时间复杂度O(mn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
           return false; 
        }
        //判断B树是否是以A节点根节点的一个子树——判断是否是子结构
        if(isTree(A,B)){
            return true;
        }
        if(isSubStructure(A.left,B) || isSubStructure(A.right,B)){
            return true;
        }
        return false;
    }
    public boolean isTree(TreeNode TA,TreeNode TB){
        if(TB == null){
            return true;
        }
        if(TA == null){
            return false;
        }
        if(TA.val != TB.val){
            return false;
        }
        return isTree(TA.left,TB.left) && isTree(TA.right,TB.right);

    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月30日上午12:41

解题思路：先遍历A的每一个节点nA，再判断B是否为nA的子树。
时间复杂度：O(MN),M表示A节点数量，N表示B节点数量
空间复杂度：O(M)

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A,B):
            if not B:
                return True
            if not A or A.val != B.val:
                return False
            return recur(A.left, B.left) and recur(A.right,B.right)

        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right, B))

0 赞同 0 条回复

Tolkien 永久会员 2022年10月29日下午11:16

/**
     * 时间复杂度：O(n*m)
     * 空间复杂度：O(logn)
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 0. 函数含义
        // 树B是树A的子结构
        // 1. 递归结束条件
        if (A == null || B == null) {
            return false;
        }

        // 2. 等价关系式
        // 树B是树A的子结构 等价于
        // 情况1: 以节点A为根节点的子树包含树B
        if (isSubTree(A, B)) {
            return true;
        }

        // 情况2：树B是树A左子树或右子树的子结构
        if (isSubStructure(A.left, B) || isSubStructure(A.right, B)) {
            return true;
        }

        return false;
    }

    // 树A中以Ta为根节点的子树是否包含以Tb为根节点的树B
    public boolean isSubTree(TreeNode Ta, TreeNode Tb) {
        // 1. 结束条件
        if (Tb == null) {
            return true;
        }

        if (Ta == null) {
            return false;
        }

        if (Ta.val != Tb.val) {
            return false;
        }

        // 2. 等价表达式
        return isSubTree(Ta.left, Tb.left) && isSubTree(Ta.right, Tb.right);
    }

0 赞同 0 条回复

派大星普通 2022年10月29日下午10:41

class Solution {
//先序遍历找到与二叉树根节点数值一样的点，然后再判断接下来的节点是否一样，不一样。
//时间复杂度O(n*m)
//空间复杂度O(n)
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null||A==null){
            return false;
        }
        if(isSub(A,B)){
            return true;
        }
        if(isSubStructure(A.left,B)||isSubStructure(A.right,B)){
            return true;
        }
        return false;
    }
    public boolean isSub(TreeNode A,TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null && B!=null){
            return false;
        }
        if (A.val != B.val) {
            return false;
        }
        return isSub(A.left,B.left) && isSub(A.right,B.right);
    }
}

0 赞同 0 条回复

Gg 普通 2022年10月29日下午9:15

 // 时间复杂度，遍历A树节点的同时遍历B树，所以为O mn
 // 空间复杂度，采用了递归，AB两树都退化为链表时，要压栈M+N次，所以为O mn
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null && B != null){
            return false;
        }
        // 判断树的根节点是否包含，递归树的左右子树是否包含
        return isContains(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    // 判断A树是否包含B树，但只考虑根节点相同的情况
    public boolean isContains(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null || A.val != B.val){
            return false;
        }
        return isContains(A.left,B.left) || isContains(A.right, B.right);
    }
}

0 赞同 0 条回复

T 普通 2022年10月29日下午9:01

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) 
            return false;
        //B子树在A的左子树中，B子树在A的右子树中，B跟A当前节点开始递归验证。
        return isSubStructure(A.left, B) || isSubStructure(A.right, B) || recur(A, B);

    }

    public boolean recur(TreeNode A, TreeNode B) {
        // B为null所以遍历结束，全部匹配返回true
        if(B == null)
            return true;
        // 越过叶子节点或者值不相等
        if(A == null || A.val != B.val)
            return false;

        return recur(A.right, B.right) && recur(A.left, B.left);
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年10月29日下午7:42

    //时间复杂度O(nm) n m 分别是ab tree的节点树
    //空间复杂度O(m) tree退化成链表的时候递归调用深度最大
    //通过前序遍历从前序遍历的第一个节点开始对比

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return checkIsSameTree(A, B)||isSubStructure(A.left, B)||isSubStructure(A.right, B);
    }

    private boolean checkIsSameTree(TreeNode tree1, TreeNode tree2) {
        if (tree2 == null) return true;
        if (tree1 == null ) return false;
        return tree1.val == tree2.val && checkIsSameTree(tree1.left, tree2.left) && checkIsSameTree(tree1.right, tree2.right);

    }

0 赞同 0 条回复

阿白普通 2022年10月29日下午7:15

1、前序遍历，A中的每个节点均作为某子树的根与B子树比较。如果以某个节点为根的子节点与B相同，则返回true
2、A中节点数n，每次比较B子树节点m，时间O（mn），空间O（1）

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == nullptr || B == nullptr)
            return false;
        if (isSubTree(A, B))//A中的每一个节点都会成为与B比较的根节点
            return true;
        if (isSubStructure(A->left, B) || isSubStructure(A->right, B))
            return true;
        return false;
    }
    bool isSubTree(TreeNode *left, TreeNode *B)
    {
        if (B == nullptr)
            return true;
        if (left == nullptr)
            return false;
        if (left->val != B->val)
            return false;
        return isSubTree(left->left, B->left) && isSubTree(left->right, B->right);

    }
};

0 赞同 0 条回复

易水寒永久会员 2022年10月29日下午4:51

//时间：O(MN). 空间O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) {
            return false;
        }
        if(helper(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)){
            return true;
        }
        return false;
    }
    private boolean helper(TreeNode A, TreeNode B) {
        if(B == null) {
            return true;
        }
        if(A == null) {
            return false;
        }
        if(A.val != B.val) {
            return false;
        }
        return helper(A.left, B.left) && helper(A.right, B.right);
    }
}

0 赞同 0 条回复

just 普通 2022年10月29日下午4:11

//递归
class Solution {
public:
bool issame(TreeNode* a,TreeNode* b){
if(bnullptr) return true;
if(anullptr || a->val!=b->val) return false;
return issame(a->left,b->left)&&issame(a->right,b->right);
}

bool isSubStructure(TreeNode* A, TreeNode* B) {
    if(!A || !B) return false;
    return ( issame(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B) );
}

};

0 赞同 0 条回复

Haoyun 普通 2022年10月29日下午2:56

var isSubStructure = function(A, B) {
    if(!A || !B) {
        return false;
    }
   const compare = function(A, B) {
      if(!B) {
          return true;
      }
      if(!A) {
          return false;
      }
      if(A.val !== B.val) {
          return false;
      }
      return compare(A.left, B.left) && compare(A.right, B.right);
   }
   if(compare(A,B)) {
       return true;
   }
   return isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

时间：O(mn)，空间：O(n)

0 赞同 0 条回复

狗蛋儿普通 2022年10月29日下午12:10

双层的前序遍历

class Solution {
public:
    bool recursion(TreeNode* root1, TreeNode* root2){
        //当一个节点存在另一个不存在时
        if(!root1 && root2)   return false;
        //两个都为空则返回
        if(!root1 || !root2 ) return true;
        //比较节点值
        if(root1->val != root2->val) return false;
        //递归比较子树
        int leftt = recursion(root1->left, root2->left);
        int rightt = recursion(root1->right, root2->right);
        return  leftt && rightt;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot2)   return false;
        if(!pRoot1  && pRoot2)  return false;
        if(!pRoot1)  return true;

        bool flag1 = recursion(pRoot1, pRoot2);  
        bool flag2 = HasSubtree(pRoot1->left, pRoot2);  
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }
};

0 赞同 0 条回复

是梦终空永久会员 2022年10月29日下午12:05

看了一下地哥讲解的思路，递归判断，直到B为空为true，如果不匹配，就判断A的left和right，直到A为null为false
时间O(n)
空间O(n)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B == null)    return false;

        if(sub(A,B))    return true;
        if(isSubStructure(A.left,B) || isSubStructure(A.right,B) )    return true;
        return false;
    }
    public boolean sub(TreeNode A,TreeNode B){
        if(B == null)   return true;
        if(A == null)   return false;
        if(A.val!=B.val)    return false;

        return sub(A.left,B.left) && sub(A.right,B.right);
    }
}

0 赞同 0 条回复

追普通 2022年10月29日上午11:07

class Solution {
public:

    bool equalv(TreeNode* A, TreeNode* B){
        if(B == nullptr) return true;
        if(A == nullptr) return false;

        if(A->val == B->val){
            return equalv(A->left, B->left) && equalv(A->right, B->right);
        }else{
            return false;
    }
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;

        if(A->val == B->val && equalv(A, B)) 
        return true;
        else
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

注意只要A的左子树包含B或者A的右子树包含B，则满足条件，因此最后的条件应该是或

0 赞同 0 条回复

黎昕普通 2022年10月29日上午9:27

剑指 Offer 26. 树的子结构

这道题目是26、27、28 三道递归中相对较难的一道题。

27题只需要对单根节点进行递归即可，不需要辅助的递归函数。

28题需要构造一个辅助递归函数，因为原本的只有一个形参的函数并不能完成需要的递归任务，官方给出的is函数并不需要成为递归函数。

26题不止需要构造一个递归函数，同时is函数与构造出来的函数都要进行递归调用，类似于一个双重循环。

思路

类似于两层循环，外层遍历所有节点，内层从遍历到目前的节点开始判断是不是一致。

和字符串匹配的暴力搜索核心思想非常像。

is函数：做深搜操作

如果a，b为空则返回false

如果aval=bval，检查a子树与b树，或者is(a右子树，b树)，或者is(a左子树，b树) //后面两个或者是比较容易忘记的

如果aval!=bval，is(a右子树，b树)，或者is(a左子树，b树) //这里是||且b树不同时向下递归，直接使用b树递归

构造的递归函数 check(a,b)

检查b树是不是可以嵌入a树并以a节点为根节点（这句话有点绕，没想好怎么写的更明白

分为五种情况：a空b空，a不空b空，a空b不空，a不空b不空(包含aval与bval是否相等两种)

a空b不空，返回false

b空返回true（隐含a空与a不空）

aval!=bval（隐含ab都不为空），返回false

avalbval（隐含ab都不为空），递归check(a-left，b-left)&&check(a-right,b-right) //这里是&& 且b树同时向下递归

注意的点上面的思路中已经用注释形式写了

复杂度

时间完全等同于字符串暴力匹配 O(M*N)，M为A树节点树，N为B树节点树
空间递归深度无论M>N或者M<\N,均为O(M)，在左倾树或者右倾树(退化为链表)时达到

其他问题

最开始卡住的原因是，自己尝试模拟的时候，如果一个节点在check的时候，从check发生处下面很多层出现失配，不应该返回check下一层开始匹配，应该考虑不需要回溯那么多层。

其实就是类似于KMP算法一样不需要回溯，这也是我为什么反复说和字符串匹配非常像。

我认为这道题应该还存在更简单的解法，类似于KMP那样的，但是还没想明白。

代码

bool check(struct TreeNode* a,struct TreeNode* b){
    if(!a&&b!=NULL)return false;
    else if(!b) return true;//隐含a空与a不空两种
    else if(a->val!=b->val)return false;//隐含ab均不空
    else return check(a->left,b->left)&&check(a->right,b->right);
}

bool isSubStructure(struct TreeNode* a, struct TreeNode* b){
    if(!a||!b)return false;
    else if(a->val==b->val)return check(a,b)||isSubStructure(a->left,b)||isSubStructure(a->right,b);
    else return isSubStructure(a->left,b)||isSubStructure(a->right,b);
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月29日上午8:44

时间复杂度O(mn) 空间复杂度O(n)

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //判断特殊条件，若A与B其中一个为空，则直接判定为false
        if(B==NULL || A==NULL) return false;
        //B为A的子结构，无非是三种情况
        //1、B是以A的根节点为根节点的子树
        //2、B的起点隐藏在A的左子树中
        //3、B的起点隐藏在A的右子树中
        return isContain(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }

    bool isContain(TreeNode* A,TreeNode* B)
    {
        if(B==NULL) return true;
        if(A==NULL || A->val!=B->val) return false;
        return isContain(A->left,B->left) && isContain(A->right,B->right);
    }
};

0 赞同 0 条回复

浅夏的无奈普通 2022年10月29日上午1:20

//时间复杂度：O(MN)
//空间复杂度：O(N)
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 若A与B其中一个为空,立即返回false
        if(A == null || B == null) {
            return false;
        }
        // B为A的子结构有3种情况,满足任意一种即可:
        // 1.B的子结构起点为A的根节点,此时结果为recur(A,B)
        // 2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
        // 3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /*
    判断B是否为A的子结构,其中B子结构的起点为A的根节点
    */
    private boolean recur(TreeNode A, TreeNode B) {
        // 若B走完了,说明查找完毕,B为A的子结构
        if(B == null) {
            return true;
        }
        // 若B不为空并且A为空或者A与B的值不相等,直接可以判断B不是A的子结构
        if(A == null || A.val != B.val) {
            return false;
        }
        // 当A与B当前节点值相等,若要判断B为A的子结构
        // 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
        // 若两者都满足就说明B是A的子结构,并且该子结构以A根节点为起点
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月29日上午12:06

时间复杂度O（nm），O（lgnlgm)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        boolean flag = f(A,B);
        if(flag) return true;
        return isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    boolean f(TreeNode A,TreeNode B){
        //B为null时，A无论为不为null，A都包含B
        if(B==null) return true;
        //B不为null，A为null,A不可能包含B了，所以返回false
        if(A==null) return false;
        //A,B都不等于null，A，B不相等，两者一定不是父子关系，返回false
        if(A.val != B.val) return false;
        //后序遍历
        return f(A.left,B.left)&&f(A.right,B.right);
    }
}

0 赞同 0 条回复

So 普通 2022年10月29日上午12:01

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        if (isSubSTree(A, B)) {
            return true;
        }
        if (isSubStructure(A.left, B) || isSubStructure(A.right, B)) {
            return true;
        }
        return false;
    }

    public boolean isSubSTree(TreeNode Ta, TreeNode Tb) {
        if (Tb == null) {
            return true;
        }
        if (Ta == null) {
            return false;
        }
        if (Ta.val != Tb.val) {
            return false; 
        }
        return isSubSTree(Ta.left, Tb.left) && isSubSTree(Ta.right, Tb.right);
    }
}

时间：O(mn)，空间：O(n)

0 赞同 0 条回复

青木普通 2022年10月28日下午11:38

/**
    只能想到把A节点逐个遍历，当A节点等于B节点，再把A和B进行一一比较，耗时较长

    时间复杂度O(m * n) m是A节点数，n是B节点数，最差情况每个节点都去比较一次
    空间复杂度O(h)  h是树的宽度
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B == null) return false;
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode node = new TreeNode();
        q.offer(A);
        while(!q.isEmpty()){
            node = q.poll();
            if(node.val == B.val){
                if(function(node, B)) return true;
            }
            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);

        }
        return false;
    }

    public boolean function(TreeNode r1, TreeNode r2) {
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode a = r1;
        TreeNode b = r2;
        q.offer(a);
        q.offer(b);
        while(!q.isEmpty()){
            a = q.poll();
            b = q.poll();

            if(a==null || a.val != b.val) return false;
            if(b.left != null){
                q.offer(a.left);
                q.offer(b.left);
            }
            if(b.right != null){
                q.offer(a.right);
                q.offer(b.right);
            }
        }
        return true;
    }
}
/**
    递归代码好简单，看一下就懂了，但就是想不到T_T

    时间复杂度O(m * n) m是A节点数，n是B节点数
    空间复杂度O(m)
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A!=null && B!=null) && (function(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    public boolean function(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A==null || A.val != B.val) return false;
        return function(A.left, B.left) && function(A.right, B.right);
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月28日下午11:13

剑指 Offer 26. 树的子结构(10.28)

/**
设A节点数为n，B节点数为m
isSubTree()的时间复杂度为O(m) 总时间复杂度为O(n*m);
空间复杂度O(m) 当树 A 和树 B都退化为链表时，递归调用深度最大。当M≤N 时，遍历树A与递归判断的总递归深度为 M ；当M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        //B是当前节点开始的子树
        if(isSubTree(A,B)) return true;
        //先序遍历每一个节点
        if(isSubStructure(A.left,B) || isSubStructure(A.right,B)) return true;
        return false;
    }
    //默认Tb是子树
    public boolean isSubTree(TreeNode Ta,TreeNode Tb){
        if(Tb == null) return true;//子树为null为真
        if(Ta == null) return false;//父树不能为null
        if(Ta.val != Tb.val) return false;
        return isSubTree(Ta.left,Tb.left) && isSubTree(Ta.right,Tb.right);
    }
}

#

0 赞同 0 条回复

【二叉树专题】剑指 Offer 26. 树的子结构

共以下 48 个回答

O(N^2) DFS 递归判断·

双层的前序遍历

剑指 Offer 26. 树的子结构

思路

复杂度

其他问题

代码

剑指 Offer 26. 树的子结构(10.28)

# 回答此问题取消回复

【二叉树专题】剑指 Offer 26. 树的子结构

共以下 48 个回答

O(N^2) DFS 递归判断·

双层的前序遍历

剑指 Offer 26. 树的子结构

思路

复杂度

其他问题

代码

剑指 Offer 26. 树的子结构(10.28)

# 回答此问题 取消回复

# 回答此问题取消回复