九号球普通 2023年11月15日下午10:31

“`java
要注意有两层递归，一个是要遍历每个节点，然后在这个节点往下遍历看是否是子结构
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 || A.val != B.val) {
        return false;
    }
    return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);

}

}

0 赞同 0 条回复

大大普通 2023年11月15日下午8:50

 //同步先序遍历
 //isSub只判读a中是否含有B的子串 不判断a的左右子树的情况
class Solution {
public:
    bool isSub(TreeNode* a,TreeNode* b){
        if(a==NULL&&b!=NULL)return false;
        if(b==NULL)return true;

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

0 赞同 0 条回复

招舟子普通 2023年8月25日下午7:04

“`java
/**
* 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;
}
return is(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
public boolean is(TreeNode A, TreeNode B){
if(B==null){
return true;
}
if(A==null){
return false;
}
if(A.val!=B.val){
return false;
}

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

}
二叉树优先考虑递归，先实现递归对比两个树，再实现递归对比树的左右子树和树

0 赞同 0 条回复

淡色花樱普通 2023年7月18日下午4:58

“`java
时间复杂度0(n)
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 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);
}

}

0 赞同 0 条回复

Bello~ 普通 2023年7月17日上午11:22

递归，时间复杂度O（MN），空间复杂度为O（M）。M为数A节点数，N为数B节点数

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

    private 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 条回复

cute. 普通 2023年7月12日下午2:45

思路：递归解决

var isSubStructure = function(A, 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;
};

var isSubTree = function(a, 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 条回复

cute. 普通 2023年7月12日下午2:45

思路：递归解决

var isSubStructure = function(A, 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;
};

var isSubTree = function(a, 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 条回复

jhfuture 普通 2023年7月10日下午7:10

java实现

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null&&B==null) {
            return true;
        }
        if(B==null||A==null) return false;
        return f(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    public boolean f(TreeNode A,TreeNode B){
        // 如果B爲空则遍历完成
        if(B==null) return true;
        // A全部遍历完B不为空
        if(A==null) return false;
        //A 与B 结点的值不相等
        if(A.val!=B.val) return false;
        // 继续判断子节点
        return f(A.left,B.left)&&f(A.right,B.right);
    }
}

太抽象了，做这个问题的时候一开始没有把握好子问题，做的头皮发麻，但做出来了感觉还是挺好的！

0 赞同 0 条回复

CV大神普通 2023年7月7日下午9:14

public boolean isSubStructure(TreeNode A, TreeNode B) {
        //只要有一个为空，则不是
        if (A ==null || B == null) {
            return false;
        }
        //分别以头部、左叶子、右叶子作为对比
        return compare(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);

    }

    public boolean compare(TreeNode A, TreeNode B){
        //B比较完了
        if(B == null) return true;
        //A比完了，或者A和B不相等，说明不是
        if((A == null ) || (A.val != B.val)) {
            return false;
        }
        //再次比较左边和右边
        return compare(A.left,B.left) && compare(A.right,B.right);
    }

时间复杂度O（mn），空间复杂度O（m）

0 赞同 0 条回复

BOZ 普通 2023年7月7日上午10:17

【思路】递归，定义一个_isSubTree函数用来从根节点匹配两个子树
【复杂度】时间复杂度O(nlogn)？

class Solution {
public:
    // match B in A from A' root
    bool _isSubTree(TreeNode* A, TreeNode* B) {
        if (B == NULL) return true;
        if (A == NULL) return false;
        if (A->val == B->val) 
            return _isSubTree(A->left, B->left) && 
                    _isSubTree(A->right, B->right);
        else return false;
    }

    // match B in A
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (B == NULL || A == NULL) return false;
        if (_isSubTree(A, B)) 
            return true;
        else
            return isSubStructure(A->left, B) ||
                    isSubStructure(A->right, B);
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日下午8:31

C++实现

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {

        if(!A && !B) return true;

        if(!A || !B) return false;

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

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

    }

    bool isSame(TreeNode* A, TreeNode* B) {
        // B 为空表示已经匹配完毕，返回 true
        if (!B) return true;

        // A 为空但B不为空或者节点值不相等，返回 false
        if (!A || A->val != B->val) return false;

        // 递归判断 A 的左子树和 B 的左子树是否相同，以及 A 的右子树和 B 的右子树是否相同
        return isSame(A->left, B->left) && isSame(A->right, B->right);
    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月5日下午4:21

定义了一个Solution类，其中包含一个isSubStructure方法。该方法接受两个参数A和B，分别表示树A和树B的根节点。该方法的返回值是一个布尔值，表示树B是否是树A的子结构。

在isSubStructure方法中，首先判断A和B是否为空，如果其中任意一个为空，则返回False。然后，调用check方法判断A和B是否相同，如果相同则返回True。接着，递归调用isSubStructure方法判断A的左子树和B是否相同，以及A的右子树和B是否相同。最后，如果以上三种情况中有任意一种返回True，则返回True；否则返回False。

在check方法中，首先判断B是否为空，如果为空，则说明B已经遍历完了，返回True。然后，判断A是否为空，如果为空，则说明A已经遍历完了，返回False。接着，判断A的值是否等于B的值，如果不等，则返回False。最后，递归调用check方法判断A的左子节点和B的左子节点是否相同，以及A的右子节点和B的右子节点是否相同。如果以上两种情况都返回True，则返回True；否则返回False。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

    def check(self, A: TreeNode, B: TreeNode) -> bool:
        if B is None:
            return True
        if not A or A.val!=B.val:
            return False
        return self.check(A.left, B.left) and self.check(A.right, B.right)

0 赞同 0 条回复

断舍离永久会员 2023年7月5日上午9:33

//看的题解，没思路
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 条回复

名字什么的好麻烦普通 2023年7月4日下午1:21

分两步

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null)
            return false;
        return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    public 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 条回复

mpweixin用户普通 2023年7月3日下午3:41

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

时间复杂度为O(MN)
空间复杂度为O(M)

0 赞同 0 条回复

mpweixin用户普通 2023年7月3日下午1:09

java
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null && B == null) {
            return true;
        }

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

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

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

        if(A.val == B.val) {
            if(B.left != null && B.right != null) { 
                return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);
            } else if(B.left == null && B.right != null) {
                return  isSubTree(A.right, B.right);
            } else if(B.left != null && B.right == null) {
                return isSubTree(A.left, B.left);
            } else {
                return true;
            }
        }
        return false;
    }

时间复杂度和空间复杂度为O(M+N)，M+N 为A, B 树的节点和

0 赞同 0 条回复

　　　　　　　　普通 2023年7月3日下午1:00

class Solution {
public:
    bool is(TreeNode* p,TreeNode* q){
        if(!q&&!p)return true;
        if(!q||!p||p->val!=q->val)return false;
        return is(p->left,q->right)&&is(q->left,p->right);
    }
    bool isSymmetric(TreeNode* root) {
        return is(root,root);
    }
};

【时间O(n),空间O(1)】
递归

0 赞同 0 条回复

局外人普通 2023年7月3日上午10:29

思路：构造辅助函数，用于检查是否包含子结构，然后灵活地运用，return不同的结果的或
时间复杂度O(n) 空间复杂度O(n)

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

0 赞同 0 条回复

地平线真勇敢普通 2023年7月2日下午4:17

public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A null || B null){
return false;
}
if(isSubTree(A, B)){ //判断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; //TB为空
if(TA null) return false; //TA为空
if(TA.val != TB.val) return false;
return isSubTree(TA.left, TB.left) && isSubTree(TA.right, TB.right);
}
时间复杂度：o(n*k)
空间复杂度：o(n)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午10:38

暴力
时间：O(mn)
空间：O(mmn)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        } 
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(A);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if (check(temp, B)) {
                return true;
            }
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        return false;
    }

    private boolean check(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        } else if (a == null || a.val != b.val) {
            return false;
        } 
        return check(a.left, b.left) && check(a.right, b.right);
    }
}

他解：递归
时间：O(mn)
空间：O(m)

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 条回复

别恰冰水🧊 永久会员 2023年6月29日上午11:19

时间复杂度为 O(n*k)。
空间复杂度：空间复杂度为树 A 的高度

bool isSubtree(struct TreeNode* a, struct TreeNode* b){
    if(b == NULL) return true;

    if(a == NULL || a->val != b->val) return false;

    return isSubtree(a->left, b->left) && isSubtree(a->right, b->right);
}
bool isSubStructure(struct TreeNode* A, struct 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;
}

0 赞同 0 条回复

～普通 2023年6月29日上午10:58

class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A nullptr || B nullptr)
return false;

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

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

}
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (q == nullptr)
        return true;
    if (p == nullptr || q == nullptr)
        return false;

    return (p->val == q->val)
           && isSameTree(p->left, q->left)
           && isSameTree(p->right, q->right);
}

};
时间复杂度 O(mn)
空间复杂度 O(m)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午7:15

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

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

0 赞同 0 条回复

江畅普通 2023年6月28日上午12:55

// 树的子结构, A 节点数 N, B 结点数 M
// 时间复杂度 O(NM)
// 空间复杂度 O(M)
class Solution {
private:
    // 判断 B 是不是 A 的子树
    bool isSubTree(TreeNode* A, TreeNode* B) {
        if (B == nullptr) {
            return true;
        }
        if (A == nullptr || A->val != B->val) {
            return false;
        }
        return isSubTree(A->left, B->left) && isSubTree(A->right, B->right);
    }

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

        return isSubTree(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月27日下午11:14

有一点思路但写不出来，看了讲解才明白
时间复杂度为 O(n*k)。
空间复杂度：空间复杂度为树 A 的高度

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

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

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

    }

    // 1. 明确函数功能 输入+输出
    public boolean isSubTree(TreeNode A, TreeNode B){
        // 2. 明确递归结束条件
        if(B == null) return true; // 一定得先判断B！！！！
        if(A == null) return false;

        // 3. 明确函数的等价关系式
        if(A.val != B.val) return false;
        return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);

    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午9:51

c++递归
bool is_container(TreeNode* A, TreeNode* B)
{
if(BNULL)return true;
if(ANULL)return false;
if(A->valB->val)return is_container(A->left,B->left)&&is_container(A->right,B->right);
else return false;
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(ANULL||BNULL)return false;
if(A->valB->val&&is_container(A,B))return true;
else
return isSubStructure(A->left,B)||isSubStructure(A->right,B);
}

0 赞同 0 条回复

屠龙手段普通 2023年6月26日下午8:31

递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

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

0 赞同 0 条回复

彦，，# 普通 2023年6月26日下午7:59

public:
    bool recur(TreeNode* A,TreeNode* B)
    {
        if(nullptr == B)  return true;
        if(A == nullptr || A->val !=B->val) return false;
        //判断B是否为A的子结构，左子树和右子树都要判断
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr || B == nullptr) return false;
        return recur(A,B)|| isSubStructure(A->left,B) ||isSubStructure(A->right,B);
    }
};

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日下午1:02

复杂度

时间复杂度: $O(MN)$，M N 为A，B的节点数。
空间复杂度: $O(M)$ ,M为A的节点数。

Code

/**
 * 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;
        return recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    public 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 条回复

désire. 普通 2023年6月26日上午9:29

C++实现
class Solution {
public:
bool compare(TreeNode* C, TreeNode* B)
{
if(B NULL) return true;
if(C NULL) return false;
if(C->val B->val){
return compare(C->left,B->left) && compare(C->right,B->right);
}
else
return false;
}
bool isSubStructure(TreeNode* A, TreeNode* B)
{
if(A NULL || B NULL) return false;
if(A->val B->val)
{
if(compare(A,B))
return true;
}
return isSubStructure(A->left,B) || isSubStructure(A->right,B);
}
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月26日上午12:36

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 时间复杂度：O(n * k)
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSame(root, subRoot):
            if not root and not subRoot:
                return True
            elif not root or not subRoot:
                return False

            return root.val == subRoot.val and isSame(root.left, subRoot.left) and isSame(root.right, subRoot.right)

        if not root:
            return False

        if root.val == subRoot.val and isSame(root, subRoot):
            return True

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

0 赞同 0 条回复

大鑫啊普通 2023年6月26日上午12:10

时间复杂度：O(n*k) n：A子树结点个数 k：B子树结点个数
1、分析判断要涉及左右子树判断，用递归
2、新建方法确定是否b为以a为头结点的子树，判断值相同则继续递归判断
3、最后递归左右子树判断B是否为A的子树中的一部分

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 条回复

行动派小彩笔普通 2023年6月25日下午11:04

时间O(A节点*B节点)，空间O(A节点)
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //if(A==NULL&&B==NULL) return true;
        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* 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 条回复

Jerry 普通 2023年6月25日下午10:36

 //递归
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return 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;
        // A.val = B.val, 接着比较A.left&right 是否 等于B.left&right
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

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

0 赞同 0 条回复

伏月三十普通 2023年6月25日下午10:06

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;
    }

    //判断Tb是否是以Ta根节点的子树
    private boolean isSubTree(TreeNode Ta,TreeNode Tb){

        //Tb检查完了，就是Ta的子树
        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);
    }
}

0 赞同 0 条回复

硬核洋葱普通 2023年6月25日下午9:47

/**
 * 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 isChildStructure(TreeNode* pA, TreeNode* pB){
        if(!pB)
            return true;
        if(!pA)
            return false;

        if(pA->val != pB->val)
            return false;

        if(isChildStructure(pA->left, pB->left) && isChildStructure(pA->right, pB->right))
                return true;
        return false;
    }

    bool recur_isSS(TreeNode* p1, TreeNode* B){
        if(p1->left)
            if(recur_isSS(p1->left, B))
                return true;
        if(p1->right)
            if(recur_isSS(p1->right, B))
                return true;
        if(p1->val == B->val)
            if(isChildStructure(p1, B))
                return true;
        return false;
    }

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

这题，重点是要弄明白怎样才算是子结构。
深度遍历，如果有A树中有某个节点与B根节点的值一致，就启动判断流程。
判断流程是A树从该节点开始，和B树一起深度遍历，所遍历到的节点，要么B树中不存在，要么B树节点的值和A树节点的值相同
遍历到B树节点为空，A树节点不为空，没关系的，也算是子结构
时间复杂度O(n * m)，因为A树第一次遍历时间复杂度为O(n)，如果调用判断流程，第二次AB树一起遍历时间复杂度为O(m)
空间复杂度为O(hA)，最差情况为从A树根节点出发，遍历到A树叶节点

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月25日下午9:17

//时间O(n * k),空间O(logn)
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if(A == null || B == null){
        return false;
    }

    if(isSubTreeWithA(A,B)){    //B是否是A的子结构，且以A开头
        return true;
    }

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

boolean isSubTreeWithA(TreeNode A,TreeNode B){
    if(A != null && B == null){  
        return true;
    }
    if(A == null && B == null){
        return true;
    }
    if(A == null && B != null){
        return false;
    }

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

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

0 赞同 0 条回复

peach 普通 2023年6月25日下午9:09

思路

判断一个树是不是另一个树的子结构，注意和子树不同
如果B是A的子树，直接返回true
但即使B不是A的子树，也有可能是子结构，看B是不是A左子树的子结构，或者是不是A右子树的子结构，递归即可

代码

 //递归解法
 //时间复杂度 O(n * k) isSubTree()函数的时间复杂度为O(k) 空间复杂度 树A高度
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false; //终止条件
        if(isSubTree(A, B)) return true; //如果B是A的子树，一定符合要求
        //但即使B不是A的子树，也可能是子结构，看是不是A左右子树的子结构
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    //这个方法是判断B是不是A的子树
    private boolean isSubTree(TreeNode A, TreeNode B){
        if(B == null) return true; //B遍历结束，或者是空树，返回true
        if(A == null) return false; //B不空，A空了，一定不是子树
        if(A.val != B.val) return false; //值不等，不符合要求
        return isSubTree(A.left, B.left) && isSubTree(A.right, B.right); //继续递归
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月25日下午9:04

// c++ 实现
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B){
            return false;
        }
        if(!A && !B){
            return true;
        }
        if(A->val == B->val && check(A->left,B->left) && check(A->right,B->right)){
            return true;
        }
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
    bool check(TreeNode* a,TreeNode* b){
        if(!b){
            return true;
        }
        if(!a){
            return false;
        }
        if(a->val == b->val && check(a->left,b->left) && check(a->right,b->right)){
            return true;
        }
        return false;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年6月25日下午8:16

C++实现

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

0 赞同 0 条回复

yxy 普通 2023年6月25日下午8:07

/**
 * 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 isSame(TreeNode* A, TreeNode* B)
    {
        if(!A&&!B) return true;
        if(!A&&B) return false;
        if(A&&!B) return true;
        if(A->val!=B->val) return false;
        return isSame(A->left, B->left)&&isSame(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        queue<TreeNode*> que;
        if(!A&&!B) return true;
        if(!A&&B) return false;
        if(A&&!B) return false;
        que.push(A);
        while(que.size())
        {
            auto x = que.front();
            que.pop();
            if(x->val==B->val)
            {
                if(isSame(x,B))
                    return true;
            }
            if(x->left)
                que.push(x->left);
            if(x->right)
                que.push(x->right);
        }
        return false;
    }
};

时间复杂度：O（n*m）
空间复杂度：O（n）

0 赞同 0 条回复

Vow the vow。普通 2023年6月25日下午7:59

有点类似对称树的思想。区别是这道题不一定是从根节点得到答案。

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

    public boolean isSameTree(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(node1 == null) return false;
        if(node2 == null) return true;
        if(node1.val != node2.val) return false;
        return isSameTree(node1.left,node2.left) && isSameTree(node1.right, node2.right);
    }

0 赞同 0 条回复

张开怀普通 2023年6月25日下午7:43

class Solution{
public:
     bool isSubStructure(TreeNode* A, TreeNode* B){
          // 若A或B为空树，则B不是A的子结构
          if (A == nullptr || B == nullptr){
                return false;
          }
          // B为A的子结构
          if (isSubTree(A,B)){
                return true;
          }
          if (isSubStructure(A->left,B) || isSubStructure(A->right,B)){
                return true;
          }
          return false;
     }
     // 判断根节点相同的Ta、Tb是否相同
     bool isSubTree(TreeNode* Ta, TreeNode* Tb){
           if(Tb == nullptr){
                 return true;
           }

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

           if(Ta->val != Tb->val){
                 return false;
           }
           // 递归判断A的左子树和B的左子树是否相等，判断A、B的右子树是否相等
           return isSubTree(Ta->left, Tb->left) && isSubTree(Ta->right, Tb->right);
     }
}

时间复杂度：O(n)
空间复杂度：A的高度

0 赞同 0 条回复

Ming 普通 2023年6月25日下午3:51

复杂度O(nm) O(n)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 如果树 A 或树 B 为空，或者树 B 是空树但树 A 不是空树，则 B 不是 A 的子结构
        if (A == null || B == null) {
            return false;
        }
        // 从根节点开始递归判断树 A 中是否存在与树 B 结构相同的子树
        return isSubTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    // 判断以节点 A 和节点 B 为根节点的两棵树是否相等
    private boolean isSubTree(TreeNode A, TreeNode B) {
        // 如果树 B 为空，则认为 B 是 A 的子树
        if (B == null) {
            return true;
        }
        // 如果树 A 为空，或者节点 A 和节点 B 的值不相等，则树 A 不是树 B 的子树
        if (A == null || A.val != B.val) {
            return false;
        }
        // 递归判断树 A 的左子树和树 B 的左子树是否相等，
        // 以及树 A 的右子树和树 B 的右子树是否相等
        return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);
    }
}

0 赞同 0 条回复

Yodl. 普通 2023年6月25日下午3:39

class Solution {
public:
    bool flag=false;//标志
    bool check(TreeNode* A, TreeNode* B)
    {
        if(A==NULL&&B==NULL)
        {
            return true;
        }
        if(A!=NULL&&B==NULL)
        {
            return true;
        }
        if(A==NULL&&B!=NULL)
        {
            return false;
        }
        if(A->val!=B->val)
        {
            return false;
        }
        return check(A->left, B->left)&&check(A->right, B->right);
    }

    //遍历树A，若遍历到和树B的根节点值相同的节点，则开始检查B是否A的子结构
    void bianli(TreeNode* A,TreeNode* B)
    {
        if(A==NULL)
        {
            return;
        }
        if(A->val==B->val)
        {
            flag=check(A,B);//开始检查
        }
        bianli(A->left,B);
        bianli(A->right,B);
        return;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL||B==NULL)
        {
            return flag;
        }
        bianli(A,B);//遍历树A
        return flag;
    }
};
时间复杂度为:O(n*k)
空间复杂度:树 A 的高度

0 赞同 0 条回复

雨落圆荷普通 2023年6月25日下午2:37

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 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);
}

}
假设树A的节点个数为 n, 树B为k，则
时间复杂度：isSubTree函数的时间复杂度为 O(k)，所以时间复杂度为 O(n*k)。
空间复杂度：空间复杂度为树 A 的高度。

0 赞同 0 条回复

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

共以下 46 个回答

复杂度

Code

思路

代码

# 回答此问题取消回复

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

共以下 46 个回答

复杂度

Code

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复