YOLO 普通 2024年3月23日下午9:16

/*输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
  */
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 条回复

HU 普通 2024年3月14日下午10:10

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    // 如果A和B同为空树，则返回false
    if(A == null && B == null) return false;

    // 如果A不为空树，B为空树，则返回false
    if(A != null && B == null) return false;

    // 如果A为空树，B不为空树，则返回false
    if(A == null && B != null) return false;

    // 如果A和B都不为空树
    if(A != null && B != null) {
        // 如果B是以A的根节点开始的A的子结构，则返回true
        // 否则，返回递归
        if(isSubTree(A, B) == true) return true;
        else return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
};

// 判断TreeB是否是以TreeA为根节点开始的TreeA的子结构
const isSubTree = (TreeA, TreeB) => {
    // 如果TreeA为空，并且TreeB为空，则返回true
    if(TreeA == null && TreeB == null) return true;

    // 如果TreeA不为空，并且TreeB为空，则返回true
    if(TreeA != null && TreeB == null) return true

    // 如果TreeA为空，并且TreeB不为空，则返回false
    if(TreeA == null && TreeB != null) return false;

    // 如果TreeA和TreeB都不为空，则开始递归判断
    if(TreeA != null && TreeB != null) {
        if(TreeA.val == TreeB.val) {
            return (isSubTree(TreeA.left, TreeB.left) && isSubTree(TreeA.right, TreeB.right));
        } else return false;
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月14日下午3:29

/**
 * 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:
    //步骤1：定义返回值和参数
    bool judge_tree(TreeNode* a,TreeNode* b){
        //步骤2：定义终止条件
        if(a==nullptr&&b!=nullptr){
            return false;
        }
        else if(a!=nullptr&&b==nullptr){
            return true;
        }
        else if(a==nullptr&&b==nullptr){
            return true;
        }
        else if(a->val!=b->val){
            return false;
        }

        //步骤3：定义遍历
        bool left=judge_tree(a->left,b->left);
        bool right=judge_tree(a->right,b->right);

        if(left&&right){
            return true;
        }
        else{
            return false;
        }

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

0 赞同 0 条回复

东普通 2024年3月12日下午8:15

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        //三种情况，A或A的左子树或A的右子树和B相等
        return(isSubStructure(A.left,B) || isSubStructure(A.right,B) || iscontain(A,B))
    }

    //包含：以A为根的数是否包含B（必须从A开始）
    public boolean 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 条回复

Let it be 永久会员 2024年3月11日下午11:04

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)return false;
if(A.val != B.val)return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}时间复杂度O（MN）空间复杂度O（M）

0 赞同 0 条回复

MARS 普通 2024年3月11日下午9:26

day7第三题

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    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)
    function recur(A: TreeNode | null, B: TreeNode | null): boolean {
        // 若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 条回复

Free 普通 2024年3月11日下午7:41

/**
 * 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 == nullptr || B == nullptr) {
            return false;
        }

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

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

        return false;
    }

    bool isSubTree(TreeNode* Ta, TreeNode* Tb) {
        if (Tb == nullptr) {
            return true;
        }

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

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

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

时空复杂度O(n)

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月10日下午6:52

class Solution {
    // 判断 B 是否是 A 的子结构
    // B 树要在结构上、数值上与 A 树的一部分完全一致才行
    // 对 A 左子遍历的同时对 B 左子进行遍历
    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);
    }

    private 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);
    }
    // 时间复杂度为 O(m * n)
    // 两棵树都要被遍历
    // 空间复杂度为 O(n)
    // 对 A 树的所有节点都要进行遍历
}

0 赞同 0 条回复

　南木普通 2024年3月10日下午4:40

时间复杂度：isSubTree函数的时间复杂度为 O(k)，所以时间复杂度为 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;
        }

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

神经蛙普通 2024年3月9日下午11:30

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

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

};
打卡

0 赞同 0 条回复

mpweixin用户普通 2024年3月9日下午10:27

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

莫～慢～待普通 2024年3月9日下午1:55

class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(Anull||Bnull)
return false;
if(isSame(A,B))
return true;
return isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
public boolean isSame(TreeNode A,TreeNode B)
{
if(Anull&&Bnull)
return true;
if(A!=null&&Bnull)
return true;
if(Anull&&B!=null)
return false;
if(A.val!=B.val)
return false;
return isSame(A.left,B.left)&&isSame(A.right,B.right);
}
}
遍历所有节点，然后对应去查子结构和当前节点的结构是否相同

0 赞同 0 条回复

方铎码农普通 2024年3月9日下午12:57

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

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

时间复杂度$O(MN)$，空间复杂度O(logM*logN) 跟树的深度有关

0 赞同 0 条回复

Jimmy 普通 2024年3月8日下午9:28

时间复杂度:
O(M * N) 分别要遍历两棵树

空间复杂度:
O(logM * logN) 跟树的深度有关，递归执行会使用函数执行栈暂存

/**
 * 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 == NULL || B == NULL){
            return false;
        }
        if(isSame(A,B)){//B和A一样时返回True
            return true;
        }
        //B和A不一样时，看B是不是和以A左右节点为根节点的子树一样
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
    bool isSame(TreeNode* Ta, TreeNode* Tb){
        if(Tb == NULL){//Tb的值与Ta值相等，且遍历完了Tb
            return true;
        }
        if(Ta == NULL){//Tb还没遍历完，Ta就遍历完了，这时候Tb肯定和Ta不一样
            return false;
        }
        if(Ta->val != Tb->val){//值不相等，不一样
            return false;
        }
        //比较Ta和Tb下的值是否相等
        return isSame(Ta->left,Tb->left) && isSame(Ta->right,Tb->right);

    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月8日下午5:58

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


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

        //注意此处是isSubStructure的递归哦 
        // if( f(A.left,B)||f(A.right,B)) return true;
        if( isSubStructure(A.left,B)||isSubStructure(A.right,B)) return true;
        return false;
    }

    public boolean f(TreeNode A, TreeNode B){
        //B为空并为true
        if(B == null){
            return true;
        }

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

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

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

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

0 赞同 0 条回复

NULL 普通 2024年3月8日下午5:29

class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A null || B null)return false; // 空树不会是以 tree1 的某个节点为根的子树具有相同的结构和节点值
return check(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean check(TreeNode a, TreeNode b){
if(b null)return true;// 终止条件
if(a null || a.val != b.val)return false;
return check(a.left, b.left) && check(a.right, b.right);
}
}

0 赞同 0 条回复

南梁陈庆之普通 2024年3月8日下午3:16

子结构，考虑一些边界情况

/**
 * 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) {
        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 条回复

mpweixin用户普通 2024年3月8日上午11:38

public boolean isSubStructure(TreeNode A, TreeNode B) {
if(Anull || Bnull) 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(Anull || A.val!=B.val) return false;
return recur(A.left, B.left)&&recur(A.right, B.right);

思路：
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\text{false}false ；
返回值：若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
以节点 A 为根节点的子树包含树 B ，对应 recur(A, B)；
树 B 是树 A 左子树的子结构，对应 isSubStructure(A.left, B)；
树 B 是树 A 右子树的子结构，对应 isSubStructure(A.right, B)；

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月8日上午10:35

打卡

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;
        if(isSubTree(A, B)) return true; // 先看根是否满足
        // 再看A的左右子树是否有个满足的
        if(isSubStructure(A->left, B) || isSubStructure(A->right, B)) return true;
        return false;
    }
private:
    // B 是否是以 A为根节点的子树，若是则递归判断A和B的左右子树
    bool isSubTree(TreeNode* A, TreeNode* B) {
        if(!B) return true; // 遍历到B的最底层，说明前面节点都满足相等，返回true
        if(!A || A->val != B->val) return false; // 1.A遍历到最底层B还没有，则一定不满足条件
                                                 // 2.AB当前不相等
        // 否则说明相等，继续遍历比较A和B的左右子树是否相等
        return isSubTree(A->left, B->left) && isSubTree(A->right, B->right);
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月8日上午5:36

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:
def equalTree(A,B):
if not B:
return True
if not A or A.val != B.val:
return False
return equalTree(A.right,B.right) and equalTree(A.left,B.left)

    if not A or not B:
        return False
    return equalTree(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

时间O(MN)
O(N)

0 赞同 0 条回复

Raphtalia. 普通 2024年3月8日上午1:20

class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A nullptr || B nullptr) return false;
if(judge(A, B)) return true;
return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool judge(TreeNode* A, TreeNode* B){
if(B nullptr) return true;
if(A nullptr || A->val != B->val) return false;
return judge(A->left, B->left) && judge(A->right, B->right);
}
};
//先序遍历+判断是否为子树。

0 赞同 0 条回复

heathhou 普通 2024年3月7日下午11:39

class Solution {
public:
    // 递归函数：判断二叉树子结构
    bool isSubStructure(TreeNode* A, TreeNode* B) {
         // 递归函数的结束条件
        if(B == nullptr || A == nullptr){
            return false;
        }
        // 递归函数的等价关系式
        if(isSubTree(A, B)){
            return true;
        }
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    // 递归函数：判断root2是否为root1的子树
    bool isSubTree(TreeNode* root1, TreeNode* root2){
        // 递归函数的结束条件
        if(root2 == nullptr){
            return true;
        }else if(root1 == nullptr){
            return false;
        }else if(root1->val != root2->val){
            return false;
        }

        // 递归函数的等价关系式
        return isSubTree(root1->left, root2->left) && isSubTree(root1->right, root2->right);
    }
};

0 赞同 0 条回复

机电皮怪永久会员 2024年3月7日下午10:54

时间复杂度O(n^2)
空间复杂度O(2n)

“`C++
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
return (A != nullptr && B != nullptr) && (tree(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
}

bool tree(TreeNode* A, TreeNode* B)
{
    if(B == nullptr)
    {
        return true;
    }
    if(A == nullptr || (A->val != B->val))
    {
        return false;
    }

    return tree(A->left, B->left) && tree(A->right, B->right);
}

};

“`

0 赞同 0 条回复

王位詮釋普通 2024年3月7日下午9:49

java
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A<span class="text-highlighted-inline" style="background-color: #fffd38;">null||B</span>null){
            return false;
        }
        if(check(A,B)){
            return true;
        }
        return isSubStructure(A.left,B)||isSubStructure(A.right,B);

<pre><code>}
public boolean check(TreeNode A ,TreeNode B){
    if(B==null){
        return true;
    }
    if(A==null){
        return false;
    }
    if(A.val!=B.val){
        return false;
    }
    return check(A.left,B.left)&&check(A.right,B.right);
}
</code></pre>

}
思路：循环判断B是否为A的以某一个节点为根节点的子树，如果是的话就是子结构，否则就不是。
判断是否为子树这块没写出来。。看来答案现在会了。

0 赞同 0 条回复

紫芝普通 2024年3月7日下午9:44

思路：递归判断A的每一个节点与B是否可能是相同的结构。

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

0 赞同 0 条回复

言之命至普通 2024年3月7日下午9:07

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){//先判断特殊情况
            return false;
        }

        if(isSubTree(A, B)){//判断B是不是以A为根节点的其中一个子树
            return true;
        }

        if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){//若B不是以A为根节点的其中一个子树，再判断B是不是A.left为根节点的一个子树 或者 A.right为根节点的一个子树
            return true;
        }

        return false;
    }

    public boolean isSubTree(TreeNode Ta, TreeNode Tb){
        if(Tb == null){//Tb已经检测完了，肯定是true
            return true;
        }

        if(Ta == null){//Tb没检测完，Ta检测完了，false
            return false;
        }

        if(Ta.val != Tb.val){//值不相等，false
            return false;
        }

        return isSubTree(Ta.left, Tb.left) && //递归判断Ta.left 与 Tb.left是否相等，Ta.right与Tb.right是否相等
               isSubTree(Ta.right, Tb.right);
    }
}

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

0 赞同 0 条回复

云无深雁影普通 2024年3月7日下午7:52

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

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

}
//递归先找到父节值相等的两个点，再递归判断其子节点是否相同。
//
//A有m个节点，B有n个，时间复杂度O(mn) 空间复杂度Om

0 赞同 0 条回复

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

共以下 27 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题取消回复

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

共以下 27 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题 取消回复

# 回答此问题取消回复