【二叉树专题】剑指 Offer 26. 树的子结构-跟着帅地玩副业，开拓第二曲线PlayOffer

谁仁普通 2023年9月11日下午5:59

bool isSubStructure(TreeNode* A, TreeNode* B) //判断是否子树结构
{
if (!B) return true;
if (!A || !B->left || !B->right) return false;
return isSame(A, B->left) && isSubStructure(A, B->right);
}

bool isSame(TreeNode* A, TreeNode* B) //判断是否同一结构
{
if (!A && !B) return true;
if (!A || !B) return false;
return A->val B->val && isSame(A->left, B->left) && isSame(A->right, B->right);
}//时间复杂度O（n），空间复杂度O（n）

0 赞同 0 条回复

黎明之前普通 2023年9月4日上午1:42

//A 节点为N B节点为M
//时间复杂度为O(NM)
//空间复杂度为O(M)
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;

}
bool isSubTree(TreeNode *Ta,TreeNode *Tb)
{
if(Tb NULL)//子节点为空
return true;
if(Ta NULL)//原节点为空
return false;
if(Ta->val!= Tb->val)//只要有一个节点不为NULL
return false;
return isSubTree(Ta->left,Tb->left)&&(isSubTree(Ta->right,Tb->right));//遍历到下一个节点
}
};

0 赞同 0 条回复

Miracle· 普通 2023年9月3日下午10:37

/**
* 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:
// 判断当A和B得根节点相同时，B和A后面的节点相同吗
bool issubTree(TreeNode A, TreeNode *B){
if (!B) return true; // 递归结束条件1，A的一个节点，B的对应位置没有，可以认为是子树
if (!A || A->val != B->val) // 递归结束条件2，B的一个节点，A的对应位置没有或者A,B对应位置节点值不同，返回false
return false;
return issubTree(A->left, B->left) && issubTree(A->right, B->right); // 继续在对应位置递归
}

// 判断B是否是A的子树
bool isSubStructure(TreeNode* A, TreeNode* B) {
    if (!A || !B) {
        return false;
    }
    // 根节点相同的话直接进入比较，根节点不相同看B是不是A的左/右子树的子结构
    return issubTree(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

};

0 赞同 0 条回复

羊毛同学普通 2023年9月3日下午10:34

打卡

/**
 * 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) {//判断B是不是A的子结构
        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的左子树或者右子树的子结构
            return true;
        return false;
    }

    bool isSubTree(TreeNode * x, TreeNode * y){
        if(y == NULL) return true;//已经把y遍历完了
        if(x == NULL) return false;//x完了 y还没完
        if(x->val != y->val)
            return false;
        return isSubTree(x->left,y->left) && isSubTree(x->right,y->right);
    }
};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月30日下午10:39

A的节点数N，B的节点数M
时间复杂度：O(NM)
空间复杂度：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(BNULL) return false;
if(ANULL) return false;
if(A->valB->val&&isin(A,B)) return true;
else return isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
bool isin(TreeNode* A,TreeNode* B){
if(BNULL) return true;
if(ANULL) return false;
if(A->valB->val)
return isin(A->left,B->left)&&isin(A->right,B->right);
else return false;
}
};

0 赞同 0 条回复

sincere 普通 2023年8月26日上午12:40

思路：isSubStructure 用于判断 B 是否为 A 的子结构，所以要判断的有 A、A.left、A.right；recur 判断 a、b 为根节点时，b 是否为 a 的子结构，此时 a、b 均为根节点，所以 ab 相等后就继续判断各自的左右子树
复杂度：时间复杂度O(Na*Nb)，空间复杂度O(Na)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;// 有一个为空肯定不是子结构
        }
        // A、B为根节点的判断；A.left、B为根节点的判断；A.right、B为根节点的判断（递归调用）
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /**
     * 判断以 a、b 为根节点时,b 是否为 a 的子结构
     */
    public Boolean recur(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;// b 走完了说明判断结束 是子结构
        }
        if (a == null || a.val != b.val) {
            return false;// b 不为空时,a 为空或者两节点值不相等都不是子结构
        }
        // 当 a、b 都不为空且值相等,则需要继续往子节点判断
        // 判断 a.left - b.left 和 a.right - b.right
        return recur(a.left, b.left) && recur(a.right, b.right);
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月25日下午6:09

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /*
    参考:数据结构与算法的题解比较好懂
    死死记住isSubStructure()的定义:判断B是否为A的子结构
    */
    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 条回复

木木普通 2023年8月22日下午2:35

時間複雜度 : O(MN) 空間複雜度 : O(M) 最差情況為遍歷所有 A的節點即為 M 個


class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
      // edge case 
      if (B == NULL || A == NULL) return false;
      /// B 為 A 的子結構有三種情況，滿足任意一種即可：
      // 1. B 的子結構起點為 A 的根節點，此時結果為 isTheSame(A, B)
      // 2. B 的子結構起點隱藏在 A 的左子樹中，而不是直接為 A 的根節點，此時結果為 isSubStructure(A->left, B)
      // 3. B 的子結構起點隱藏在 A 的右子樹中，此時結果為 isSubStructure(A->right, B)
      return isTheSame(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    bool isTheSame(TreeNode* root, TreeNode* subroot) {
      if ( subroot == NULL) return true;
      if (root == NULL || subroot == NULL) return false;

      if (root == NULL || root->val != subroot->val) {
        return false;
      }
    // 當 A 與 B 當前節點值相等時，若要判斷 B 為 A 的子結構
    // 還需要判斷 B 的左子樹是否為 A 左子樹的子結構，以及 B 的右子樹是否為 A 右子樹的子結構
    // 若兩者都滿足，就說明 B 是 A 的子結構，且該子結構以 A 根節點為起點

      return isTheSame(root->left, subroot->left) && isTheSame(root->right, subroot->right);

    }
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月21日下午7:48

java版

    //树的子结构
    //输入两棵树，判断B是不是A的子结构（约定空树不是任意一个树的子结构）
    public boolean isSame(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null && B != null) return false;
        return (A.val == B.val) && isSame(A.left, B.left) && isSame(A.right, B.right);
    }
    //遍历所有子树
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;

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

0 赞同 0 条回复

辰北、普通 2023年8月21日上午11:43

////俩函数，找到与子支相同的root，代入isame比较，对左右支进行递归对比，返回ture就是子支，
bool isSameNode(struct TreeNode* A, struct TreeNode*B){
if(B NULL)
return true;
else if(ANULL)
return false;
else if(A->val B->val)
return(isSameNode(A->left,B->left) && isSameNode(A->right,B->right));
return false;
}

bool isSubStructure(struct TreeNode* A, struct TreeNode* B){

if(BNULL || ANULL)
return false;
if(A->val B->val){
if(isSameNode(A,B))
return true;
else
return(isSubStructure(A->left,B) || isSubStructure(A->right,B));
}
else{
return(isSubStructure(A->left,B) || isSubStructure(A->right,B));
}
return true;
}

0 赞同 0 条回复

逸兴遄飞普通 2023年8月21日上午10:59

时间复杂度 O(MN) ，M为A节点数，N为B节点数
空间复杂度 O(M)，所有情况均为遍历完A节点数结束

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 均为空树则false
        if(A == null || B ==  null) return false;
        // 查看三点判断为true
        // 1、B的子结构起点为A的根节点
        // 2、B的子结构起点隐藏在A的左子树中
        // 3、B的子结构起点隐藏在A的右子树中
        return isContain(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isContain(TreeNode A, TreeNode B) {
        // 前面相同，B走完了，说明B为A的子结构
        if(B == null) return true;
        // A走完了B还没走完，或者有值不同的节点，说明不是
        if(A == null || A.val != B.val) return false;
        // 进行递归操作，判断B当前节点的左右子树是否为A当前节点的左右子树的子结构
        return isContain(A.left, B.left) && isContain(A.right, B.right);
    }
}

0 赞同 0 条回复

小肸永久会员 2023年8月20日下午10:05

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //用例: A=[],B=[],结果为false
        return (A != null && B != null) && (dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    private boolean dfs(TreeNode root, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        return root.val == B.val && dfs(root.left, B.left) && dfs(root.right, B.right);
    }
}

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月20日上午11:20

写的时候思路没问题，但没有搞清楚如何把A的遍历和找子结构的函数结合起来，一开始的想法是，先写一个递归函数将A中与B的root节点相同的节点找到，然后再写一个递归函数去递归比较二者的子结构，实际上本身题目给的比较是否是子结构的函数，就可以实现递归遍历A节点，每次A的节点变动一下，以它为根的A的结构就去和B比较（也就是调用另一个函数），那么返回true的情况就是要么以A为根的满足或者是A.left为根满足或者是A.right为根满足。

class Solution:
# def isroot(self, A: TreeNode, B: TreeNode) -> TreeNode:
# if not B:
# return None
# root = B
# if not A.left:
# if A.val != B.val:
# root = self.isroot(A.left,B)
# if not A.right:
# if A.val != B.val:
# root = self.isroot(A.right,B)

#     return root

def issame(self, A: TreeNode, B: TreeNode) -> bool:
    if not B:
        return True
    if not A or A.val != B.val:
        return False

    return self.issame(A.left, B.left) and self.issame(A.right, B.right)


def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
    return bool(A and B) and (self.issame(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月19日下午1:58

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

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

            }
            if (B.right != null) {
                r = isContinued(A.right, B.right);

            }
            if (l && r) {
                return true;
            }

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

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

    } 
}

0 赞同 0 条回复

c 普通 2023年8月19日下午1:34

让a的每个点都去尝试与B匹配

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

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月18日下午11:14

打卡

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    public boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月18日下午10:00

1、树一般都用递归解决

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


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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月18日下午8:06

// 时间复杂度O(mn),空间复杂度O(n+m)
 // TIP：B是空树，不是子结构
class Solution {
public:
    bool recur(TreeNode* A,TreeNode* B) //递归时间fuzaduO(m)
    {
        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);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) { //递归的时间复杂度O(n)
        if(A==NULL||B==NULL) return false;  

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

0 赞同 0 条回复

JustRtn 普通 2023年8月18日下午6:23

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

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

    bool findSameNodeAndCheck(TreeNode *root, TreeNode* b) {
        if (root == nullptr) {
            return false;
        }

        if (root->val == b->val) {
            if (isCover(root, b)) {
                return true;
            }
        }

        return findSameNodeAndCheck(root->left, b) || findSameNodeAndCheck(root->right, b);
    }

    bool isCover(TreeNode* A, TreeNode* B) {
        if (B == nullptr) {
            return true;
        }

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

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

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

0 赞同 0 条回复

帝心引力永久会员 2023年8月18日下午3:14

时间o(n). 空间o(n)
bool isSame(TreeNode* rootA, TreeNode* rootB) {
        if (!rootB) return true; // B遍历完，说明B是A的子结构
        if (!rootA || rootA->val != rootB->val) return false;

        return isSame(rootA->left, rootB->left) && isSame(rootA->right, rootB->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL) return false;
        if(isSame(A, B)) return true;

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

0 赞同 0 条回复

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

共以下 20 个回答

# 回答此问题取消回复

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

共以下 20 个回答

# 回答此问题 取消回复

# 回答此问题取消回复