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

桎梏普通 2023年8月11日下午10:12

public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;  //若A与B其中一个为空,立即返回false
        /**
        B为A的子结构有3种情况,满足任意一种即可:
        1.B的子结构起点为A的根节点,此时结果为isContain(A,B)
        2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
        3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
         */
        return isContain(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    public boolean isContain(TreeNode A,TreeNode B){
        if(B==null) return true;//若B走完了,说明查找完毕,B为A的子结构
        // 若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  isContain(A.left,B.left)&&isContain(A.right,B.right);
    }

0 赞同 0 条回复

hi 普通 2023年8月8日下午10:01

从A根节点开始判断B树是不是以此根节点的子树
弄清子树和子结构函数的区别

/**
 * 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;
        //1. 判断B子树是否以A树当前节点为根节点的子树
        if(isSubtree(A, B)) return true;
        //不是的话递归判断B是不是以A当前节点的左节点（或右节点）为根节点的子结构
        if(isSubStructure(A -> left, B) || isSubStructure(A -> right, B)) return true;
        return false;
    }
        //2. 定义新函数，判断B子树是否为当前A节点为根节点的子树
        bool isSubtree(TreeNode* a, TreeNode* b)
        {
            if(!b) return true;
            if(!a) return false;
            if(a -> val != b -> val) return false;
            return isSubtree(a -> left, b -> left) && isSubtree(a -> right, b -> right);
        }
};

0 赞同 0 条回复

今天没时间刷题普通 2023年7月31日下午11:30

时间On*m 空间On*m
lass Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!B || !A) return false;
        bool flag{false};
        dfs(A, B, flag);
        return flag;
    }

    void dfs(TreeNode* root, TreeNode* rootB, bool& flag)
    {
        if(!root) return;
        if(root->val == rootB->val)
        {
            flag |= isSame(root, rootB);
        }
        dfs(root->left, rootB, flag);
        dfs(root->right, rootB, flag);
        return;
    }

    bool isSame(TreeNode* rootA, TreeNode* rootB)
    {
        if(!rootB) return true;
        if(!rootA) return false;
        if(rootA->val != rootB->val) return false;

        return isSame(rootA->left, rootB->left) && isSame(rootA->right, rootB->right);
    }
};

0 赞同 0 条回复

小季同学普通 2023年7月26日下午9:52

ty

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    // 边界判断
    if(A === null || B === null) {
        return false
    }
    // 判断B是否是以A为节点的子树
    if(isSubTree(A, B)) {
        return true
    }

    // 根节点不是，判断左右子树
    if(isSubStructure(A.left, B) || isSubStructure(A.right, B)) {
        return true
    }

    return false

    function isSubTree (TA: TreeNode, TB: TreeNode): boolean  {
        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年7月20日下午8:56

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

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

通过

0 赞同 0 条回复

Terence💧 普通 2023年7月18日下午10:50

树的子结构

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if B == nil || A == nil  {
        return false
    }
    if B.Val == A.Val && (recur(A.Left, B.Left) && recur(A.Right, B.Right)){
        return true
    }
    return isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func recur(A *TreeNode, 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)
}

0 赞同 0 条回复

doordie. 普通 2023年7月18日下午4:42

树的子结构

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 || A.val != B.val) {
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);

    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月18日下午12:16

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

终止条件，如果A或者B有一个不存在就是false。否则判断三种情况，1. B是否是A根节点树的子结构； 2. ~A左子树~；3. ~A右子树~；
时间O(MN),空间O(M);

0 赞同 0 条回复

ppopp 普通 2023年7月18日上午12:16

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

    if(!B || !A) return false;
    return check(A,B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

};//补

0 赞同 0 条回复

普通 2023年7月17日下午9:20

c++ 代码递归判断
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(ANULL||BNULL) return false;
return isT(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);

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

}

};

0 赞同 0 条回复

Mby 普通 2023年7月17日下午7:21

/**
 * 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)){//判断B是不是以A为根节点的子结构
            return true;
        }

        if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){//判断B是不是A的左右子树的子结构
            return true;
        }

        return false;
    }


    public boolean isSubTree(TreeNode Ta, TreeNode Tb){
        if(Tb == null){//Tb比对完了说明是其子结构
            return true;
        }

        if(Ta == null){//Ta比对完了说明不是其子结构
            return false;
        }

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

        return isSubTree(Ta.left, Tb.left) &&
               isSubTree(Ta.right, Tb.right);//判断是否是其左右子树
    }
}

0 赞同 0 条回复

片言莫语普通 2023年7月17日下午6:29

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false; // 如果 A 或 B 为空树，则 B 不是 A 的子结构，返回 false
        }

        if(isSubTree(A, B)){
            return true; // 如果 B 是 A 的子树，返回 true
        }

        if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
            return true; // 递归检查 A 的左子树和右子树是否存在与 B 相同的子结构
        }

        return false; // 若未找到 B 的子结构，返回 false
    }

    public boolean isSubTree(TreeNode Ta, TreeNode Tb){
        if(Tb == null){
            return true; // 若 Tb 为空树，则 Tb 是任何树的子树，返回 true
        }

        if(Ta == null){
            return false; // 若 Ta 为空树，则 Ta 不可能是 Tb 的子树，返回 false
        }

        if(Ta.val != Tb.val){
            return false; // 如果 Ta 和 Tb 的节点值不相等，则 Tb 不是 Ta 的子树，返回 false
        }

        return isSubTree(Ta.left, Tb.left) && // 递归检查 Ta 和 Tb 的左子树是否相同
               isSubTree(Ta.right, Tb.right); // 递归检查 Ta 和 Tb 的右子树是否相同
    }
}

0 赞同 0 条回复

北辰普通 2023年7月17日上午12:13

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

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

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

            return false;
    }

    public boolean subTree(TreeNode Ta, TreeNode Tb) {
            if(Tb==null) return true;
            if(Ta==null) return false;
            if(Ta.val!=Tb.val) return false;

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

思路：第一个函数控制在A树的哪一个子树，第二个函数是判断在当前情况下，A子树与B是否相同

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月16日下午11:07

 */
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){
        // 判断是否是子结构，而不是相等
        // 当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（n*k）
空间复杂度：树A的高度

0 赞同 0 条回复

艺普通 2023年7月16日下午10:26

“`c++
//时间复杂度O(nm)
//空间复杂度O(n)
class Solution {
public:
bool dfs(TreeNode *a,TreeNode *b)
{
if(b==NULL) return true;
if(a==NULL) return false;
if(a->val!=b->val) return false;
return dfs(a->left,b->left)&&dfs(a->right,b->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==NULL||B==NULL) return false;
if(dfs(A,B)) return true;
if(isSubStructure(A->left,B)||isSubStructure(A->right,B)) return true;
return false;
}
};
“`

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月16日下午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 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 条回复

神经蛙普通 2023年7月16日下午3:00

 /**
    时间复杂度O(nm)
    空间复杂度O(n)
    前序遍历
*/
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) {
        // B为空，遍历完成，是子结构
        if (B == null) {
            return true;
        }
        // A为空或A不等于B，不是子结构
        if (A == null || A.val != B.val) {
            return false;
        }

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

0 赞同 0 条回复

Marshan 普通 2023年7月16日上午11:29

//看了解析才会
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B){
            return false;
        }
        return isSubTree(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
    bool isSubTree(TreeNode *Ta,TreeNode *Tb){
        if(!Tb){
            return true;
        }
        if(!Ta || Ta->val != Tb->val){
            return false;
        }
        // if(Ta->val != Tb->val){
        //     return false;
        // }
        return isSubTree(Ta->left,Tb->left) && isSubTree(Ta->right,Tb->right);
    }

};

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日上午9:55

“`cpp
class Solution {
public:
bool isSub(TreeNode* nodeA, TreeNode* nodeB){
if((nodeA==nullptr && nodeB == nullptr) || (nodeA !=nullptr && nodeB == nullptr)){
return true;
}
if(nodeA == nullptr && nodeB !=nullptr){
return false;
}

    if(nodeA->val != nodeB ->val){
        return false;
    }
    return isSub(nodeA->left, nodeB->left) && isSub(nodeA->right,nodeB->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
    if(A == nullptr && B==nullptr){
        return true;
    }
    if(A==nullptr || B==nullptr){
        return false;
    }
    stack<TreeNode*> stkA;
    TreeNode* nodeA = A;
    TreeNode* nodeB = B;
    while(!stkA.empty() || nodeA!=nullptr){
        while(nodeA != nullptr){
            if(nodeA->val == nodeB->val){
                TreeNode* curA = nodeA;
                TreeNode* curB = nodeB;
                if(isSub(curA, curB)){
                    return true;
                }
            }
            stkA.push(nodeA);
            nodeA = nodeA -> left;
        }
        nodeA = stkA.top();
        stkA.pop();
        nodeA = nodeA->right;
    }
    return false;
}

};

“`cpp
时间： O（mn）空间： O（mn)

0 赞同 0 条回复

周小二普通 2023年7月16日上午2:04

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

    private 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年7月15日下午10:38

用两个递归

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    if (!A && !B) {
        return true;
    } else if (!A || !B) {
        return false;
    }
    return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};


function dfs(left: TreeNode | null, right: TreeNode | null) {
    if (!left && !right) return true;
    if (!left && right) return false;
    if (left && !right) return true;
    if (left.val !== right.val) return false;
    return dfs(left.left, right.left) && dfs(left.right, right.right);
}

0 赞同 0 条回复

June 普通 2023年7月15日下午9:18

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {

    if A == nil || B == nil {
        return false
    }
    return findNode(A,B)

}

func findNode(node *TreeNode, B *TreeNode) bool {
    if node == nil {
        return  false
    }
    var ans bool = false
    if node.Val == B.Val { 
        ans = compareTree(node,B)
    }
    ans = ans || findNode(node.Left,B) || findNode(node.Right,B)
    return ans
}

func compareTree(root1 *TreeNode ,root2 *TreeNode) bool {
    var ans bool = true
    if (root1 == nil && root2 == nil) || (root1 != nil && root2 == nil) {
        return true  //都到达了叶子或者子结构结束了
    }

    if (root1 == nil && root2 != nil) || (root1.Val != root2.Val) {
        return false
    } 

    ans = compareTree(root1.Left,root2.Left) && compareTree(root1.Right,root2.Right)
    return ans

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月15日下午8:14

Day7：下面是代码

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

AD钙奶普通 2023年7月15日下午3:49

关键点要区分子结构和子树的区别，子结构可以是子树的一部分。
这里用了两层递归。
isSubStructure 含义是 B是否为A的子结构
cmp 含义是 B是否为A的子结构 并且 B的子结构起点是A的根节点
区别就在于后面那一句话，要牢牢记住这两个函数的含义。
B为A的子结构，分3种情况：
1. B的子结构起点是A的根节点
2. B的子结构起点在A的左子树中
3. B的子结构起点在A的右子树中

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

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

0 赞同 0 条回复

Mooby 普通 2023年7月15日下午2:29

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

#00456B 普通 2023年7月14日下午11:01

/**
 * 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){//有一棵树为空，返回false
            return false;
        }
        if(isSub(A,B)){//如果A和B完全一致
            return true;
        }
        if(isSubStructure(A->left, B) || isSubStructure(A->right, B)){//如果A的左子树或者右子树与B相同
            return true;
        }
        return false;
    }

    // isSub用来判断B是否被A包含
    // 逻辑为，如果A和B都相等，那么返回True，如果不相等就返回False
    bool isSub(TreeNode* A, TreeNode* B){
        if(B == NULL){//如果B都遍历完了，说明B一定是A的子树
            return true;
        }
        if(A == NULL){//因为在B==NULL的判断之后，所以如果A==NULL，说明B一定还有没遍历完的，说明不是子树
            return false;
        }
        if(A->val != B->val){//如果AB的val不一样，那么一定是false
            return false;
        }
        return isSub(A->left,B->left) && isSub(A->right,B->right);//判断左右两个节点是否一致
    }
};

0 赞同 0 条回复

阿尚普通 2023年7月14日下午8:38

//判断子结构
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;

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

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

    public boolean travel(TreeNode A, TreeNode B){
        if(A == null && B == null) return true;
        if(A == null) return false;
        if(B == null) return true;
        if(A.val != B.val) return false;

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

0 赞同 0 条回复

CaCO3 永久会员 2023年7月14日下午8:15

”’java
class Solution {
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){
if(B null){
return true;
}
if(A null){
return false;
}
return A.val B.val && compare(A.left,B.left) && compare(A.right,B.right);
}
}
”’
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

Luminous 普通 2023年7月14日下午6:41

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

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

0 赞同 0 条回复

CKX 普通 2023年7月14日下午6:04

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

    if traverse(A, B) {
        return true
    }

    if isSubStructure(A.Left, B) || isSubStructure(A.Right, B) {
        return true
    }

    return false
}

func traverse(Ta, Tb *TreeNode) bool {
    if Tb == nil {
        return true
    }

    if Ta == nil {
        return false
    }

    if Ta.Val != Tb.Val {
        return false
    }

    return traverse(Ta.Left, Tb.Left) && traverse(Ta.Right, Tb.Right)

}

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月14日下午5:24

class Solution {
boolean jude =false;
public boolean isSubStructure(TreeNode A, TreeNode B) {
//遍历A 如果命中同时遍历B
if(Anull||Bnull)
{
return false;
}
if(A.valB.val)
{
jude=isSubStructure1(A,B);
}
return isSubStructure(A.left,B)||isSubStructure(A.right,B)||jude;

}
public boolean isSubStructure1(TreeNode A,TreeNode B)
{
    if(B==null)//b为null表示结束 a可以为null 也可以不为null 因为b是子结构
    {
        return true;
    }
    if(A==null&&B!=null)//
    {
        return false;
    }
    if(A.val!=B.val)
    {
        return false;
    }
    return isSubStructure1(A.left,B.left)&&isSubStructure1(A.right,B.right);
}

}

0 赞同 0 条回复

Recluse 普通 2023年7月14日下午5:18

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

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

Fighting boy😀 普通 2023年7月14日下午5: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 is_contain(TreeNode A, TreeNode* B) {
if(Bnullptr) return true;
if(Anullptr) return false;

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

// 判断A是否包含B，包含返回ture,不包含返回false;
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(Anullptr || Bnullptr) return false;

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

};

0 赞同 0 条回复

ONE PIECE 普通 2023年7月14日下午5:05

/**
 * 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 || a.val!=b.val) return false;
        return is(a.left,b.left) && is(a.right,b.right);
    }
}

时间复杂度：O(n)

0 赞同 0 条回复

V2ero 普通 2023年7月14日下午3:21

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

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    if (!A || !B) {
        return false;
    }

    const dfs = (A: TreeNode | null, B: TreeNode | null) => {
        if (!B) {
            return true;
        }
        if (!A) {
            return false;
        }
        return A.val === B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    };

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

0 赞同 0 条回复

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

共以下 35 个回答

树的子结构

# 回答此问题取消回复

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

共以下 35 个回答

树的子结构

# 回答此问题 取消回复

# 回答此问题取消回复