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

岱永久会员 2024年12月28日下午7:56

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 若A与B其中一个为空,立即返回false
        if(A== null ||B == null) return false;
        // B为A的子结构有3种情况,满足任意一种即可:
        // 1.B的子结构起点为A的根节点,此时结果为recur(A,B)
        // 2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
        // 3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    /*
    判断B是否为A的子结构,其中B子结构的起点为A的根节点
    */
    private boolean recur(TreeNode A, TreeNode B) {
        // 若B走完了,说明查找完毕,B为A的子结构
        if(B == null) {
            return true;
        }
        // 若B不为空并且A为空 或者 A与B的值不相等,直接可以判断B不是A的子结构
        if(A == null || A.val != B.val) {
            return false;
        }
        // 当A与B当前节点值相等,若要判断B为A的子结构
        // 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
        // 若两者都满足就说明B是A的子结构,并且该子结构以A根节点为起点
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

0 赞同 0 条回复

LovLe 普通 2024年12月22日下午2:29

要么A,B匹配上，要么B与A的子结构匹配。两个递归

# 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
class Solution:
    def recur(self,A,B):
        if not B: return True
        if not A or A.val !=B.val: return False
        return self.recur(A.left,B.left) and self.recur(A.right,B.right)    #如果A,B的值都相等，那么继续比较子结构是否相等

    def isSubStructure(self, A: Optional[TreeNode], B: Optional[TreeNode]) -> bool:
        if A and not B: return False
        if not A and B: return False
        if not A and not B: return False
        return (A and B) and (self.recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))   # A,B同时都存在，要么A,B匹配上，要么B与A的子结构匹配。两个递归

0 赞同 0 条回复

mpweixin用户普通 2024年12月15日上午11:28

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(B==NULL) return false;
        stack<TreeNode*> s;
        while(A){
            if(A->val == B->val){
                bool result = compare(A,B);
                if(result) return true;
            }
            s.push(A);
            A = A->left;
            while(A == NULL && !s.empty()){
                A = s.top();
                s.pop();
                A = A->right;
            }
        }
        return false;
    }
    bool compare(TreeNode* A, TreeNode* B){
        if(A == NULL && B == NULL) return true;
        if(A && B){
            if(A->val != B->val) return false;
            bool right = compare(A->right,B->right);
            bool left = compare(A->left,B->left);
            return right && left;
        }
        else if(A && !B) return true;
        else return false;
    }
};

思路：先遍历A树找到与B树根节点值相同的节点，再以B树为主判两者是否相同结构
时间O(N*N)，空间O(N)

0 赞同 0 条回复

陆狗陆狗普通 2024年12月4日上午10:13

题解
原本函数：做一些临界值的判断(特别是空树不属于其他树的子结构，因为新建函数空树属于其他树的子结构(考虑到尾节点))，原本函数还要在当前节点不满足条件时，过度到左子树或者右子树继续判断
新建函数：不去考虑左子树或者右子树的过度（因为原本函数已经做了这个工作），只需要专注于判断2个子树是否相等

class Solution {
    // 为什么要分成2层？因为递归的退出条件和“空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 ”是矛盾的
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 临界点
        if (A==null || B == null) {
            return false;
        }
        if(isSubTree(A,B)){
            return true;
        }
        // isSubStructure外层来控制左右子节点的移动了，所以isSubTree只需要聚焦于是否是子树的判断
        if(isSubStructure(A.left,B) || isSubStructure(A.right,B)){
            return true;
        }
        return false;
    }

    public boolean isSubTree(TreeNode A, TreeNode B) {
        // B可以为空，A不能为空,B为空的时候，默认就是A的子树了
        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 条回复

Tom Yuan 普通 2024年12月3日下午4:04

方法递归判断左右子树

class Solution:
    def isSubTree(self, A, B):
        if not B: return True

        if not A: return False

        if A.val != B.val: return False

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

    def isSubStructure(self, A: Optional[TreeNode], B: Optional[TreeNode]) -> bool:
        if not A or not B: return False

        if self.isSubTree(A, B):
            return True

        if self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B):
            return True

        return False

time O(n) space O(n)

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午8:58

递归，检验各个节点

class Solution {
    public boolean isSameStructure(TreeNode root1, TreeNode root2) {
        if (root2 == null) return true;
        if (root1 == null || root1.val != root2.val) return false;
        return isSameStructure(root1.left, root2.left) && isSameStructure(root1.right, root2.right);
    }

    public boolean isSubStructure(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) return false;
        return isSameStructure(root1, root2) || isSubStructure(root1.left, root2) || isSubStructure(root1.right, root2);
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午7:32

/**
方法一：递归
B逐个与A的每个节点进行check是否有相同结构，时间复杂度O(n**2)
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {

        boolean res = false;
        if (A != null && B != null){
            res = check(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
        return res;


    }

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

    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月29日下午9:24

思路：看了leetcode评论做的，大体思路通过递归判断当前结点与他的左右结点是否能与子树进行匹配，匹配的思路是同样通过递归，终止条件：当子树的结点遍历到空，说明完成匹配，当母树遍历到空，或者当前两树对应结点的值不相等，说明不匹配。否则的话依次对两树对应结点进行依次匹配。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        else return (recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));
    }

    boolean recur(TreeNode A,TreeNode B){
        if(B==null) return true;
        else if(A==null || A.val!=B.val) return false;
        else return recur(A.left,B.left)&&recur(A.right,B.right);
    }
}
m为母树结点树，n为子树结点树
时间复杂度：o(mn)
空间复杂度：o(m)

0 赞同 0 条回复

Jerry 普通 2024年11月29日下午2:36

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

    }
    bool isSubStructureHelper(TreeNode* a, TreeNode* b){
        if(!b) return true;
        if(!a) return false;
        if(a->val == b->val){
            return isSubStructureHelper(a->left, b->left)&&isSubStructureHelper(a->right, b->right);
        }
        return false;
    }
};

时间o(mn)
空间o(n)
注意：1、递归函数B树为空（代表B树遍历完成），返回true；原函数中B树为空时（起始root为空），应该返回false；；这块边界条件自己卡了很久，需要注意。2、最开始用原函数的定义进行递归，导致找到是跟B树有相同位置结构的“子序列”树，而不是严格的子树，这块也需要注意

0 赞同 0 条回复

黑键〰普通 2024年11月29日上午11:39

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    if(!A || !B) return false
    const cpr = (p, q) => {
        if(!q) return true
        if(!p) return false
        // 递归比较当前两个节点的左右节点
        return p.val === q.val && cpr(p.left, q.left) && cpr(p.right, q.right)
    }
    // 三个内容的或，分别是根节点，左子树，还是右子树中，去递归找是否有匹配B树的子结构
    return cpr(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

思路：看完解答之后才写出来的
自己写递归的时候总是对反向往回推出问题，思路转换为代码的时候会卡壳
其实本质上都是很固定的逻辑，就是根节点，左子树，右子树，分别来比较即可
逐层往下的左右子树继续寻找对比。

0 赞同 0 条回复

Renasc 普通 2024年11月29日上午10:02

时间复杂度O(Mn),空间复杂度O(H)

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 static 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年11月28日下午9:02

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(q == nullptr) {
            return true;
        }
        if(p == nullptr) {
            return false;
        }
        return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) { 
        if(A == nullptr || B == nullptr) {
            return false;
        }
        if(isSameTree(A,B) == false) {
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
        }
        return true;
    }
};
时间复杂度 O(mn) m n 分别为treeA和 treeB 的节点数量
空间复杂度 O(m)

0 赞同 0 条回复

苯庸普通 2024年11月28日下午8:38

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

boolean dfs(TreeNode a, TreeNode b){
    if(b == null) return true;
    if(a == null) return false;
    return a.val == b.val && dfs(a.left, b.left) && dfs(a.right, b.right);
}

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Kisara 普通 2024年11月28日下午7:55

没思路写了一个方法把自己绕进去了，看了题解，明白了，先抽出一个函数判断整个树是否有结构相同的一块，然后不断递归判断三种情况

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //首先都不能为空，其次判断以A的根为根的子树有没有，其次A的左右子树为根的子树有没有，这里就涉及到递归
        return (A!=null&&B!=null)&&(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;
        //递归判断A B每个节点值想不想同
        return recur(A.left,B.left)&&recur(A.right,B.right);
    }
}

on on

0 赞同 0 条回复

Aatorx 永久会员 2024年11月28日下午4:39

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL){
            return false;
        }
// 找到相同的根节点后判断是否是子树，若不是则继续搜索，若是则直接返回
        if(A->val == B->val){
            if (recur(A, B)){
                return true;
            }
        }
// 递归寻找值相同的根节点
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
// 找到根节点后判断是否是子树
    bool 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 条回复

月下足迹普通 2024年11月28日上午11:43

class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 如果任一树为空，则直接返回false
if (A null || B null) {
return false;
}
// 检查从当前节点A开始是否包含与B相同的子树结构，或者递归检查A的左或右子树
return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

private boolean isSame(TreeNode a, TreeNode b) {
    // 如果子树B已经递归完成，说明所有匹配成功
    if (b == null) {
        return true;
    }
    // 如果子树B还未完成，而树A已经为空，或者两者的值不相等，则不匹配
    if (a == null || a.val != b.val) {
        return false;
    }
    // 递归比较两者的左右子树
    return isSame(a.left, b.left) && isSame(a.right, b.right);
}

}

0 赞同 0 条回复

jaron 普通 2024年11月28日上午11:12

class Solution {
    // b是否以a的某一个节点为子结构
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    // b是不是a的子结构
    public boolean isSame(TreeNode A, TreeNode B) {
        // b没有就不要求a有
        if (B == null)
            return true;
        // b有的话a一定要有
        if (A == null)
            return false;
        if (A.val!= B.val)
            return false;
        return isSame(A.left, B.left) && isSame(A.right, B.right);
    }
}

0 赞同 0 条回复

youngsir 普通 2024年11月28日上午10:06

打卡

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr ||B == nullptr){
            return false;
        }
        if(A->val == B->val && check(A,B)){
            return true;
        }else{
            return isSubStructure(A->left,B) || isSubStructure(A->right,B);
        }

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

0 赞同 0 条回复

lQl 永久会员 2024年11月28日上午12:04

递归,关键在于回调,如果不匹配则回调为原来的B
时间复杂度O(mn)
空间复杂度(m)

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

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

    }
}

0 赞同 0 条回复

晓宇普通 2024年11月27日下午9:11

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


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

};

// 思路：分两阶段，①先寻找B是否是A当前节点的子结构；②递归寻找B是否是A字节的子结构。

// 时间复杂度：o(n)

// 空间复杂度：o(log n)

0 赞同 0 条回复

秋山丽奈普通 2024年11月27日下午8:49

思路：首先找到与B具有相同val的结点rootB 然后比较两棵子树是否相同
问题：在最初为意识到存在相同元素，因此未能通过，通过添加循环结构，找到所有具有 B.val 的结点判断
代码复杂度较高

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

        TreeNode rootB = find(A, B.val);
        boolean temp = false;
        while(rootB != null){
            temp = checkEqual(rootB, B);
            if(temp) return temp;
            System.out.println(temp);
            // 当前节点 失败 
            rootB.val = Integer.MIN_VALUE;
            rootB = find(A, B.val);

        }
        return temp;

    }

    TreeNode find(TreeNode node, int val){
        if(node == null){
            return null;
        }

        if(node.val == val){
            return node;
        }

        TreeNode checkLeft = find(node.left, val);
        if(checkLeft != null){
            return checkLeft;
        }

        TreeNode checkRight = find(node.right, val);
        return  checkRight; 
    }

    boolean checkEqual(TreeNode nodeA, TreeNode nodeB){
        if(nodeA == null && nodeB == null){
            return true;
        }

        if(nodeA != null && nodeB == null){
            return true;
        }

        if(nodeA == null && nodeB != null){
            return false;
        }

        if(nodeA.val == nodeB.val){
            return checkEqual(nodeA.left, nodeB.left) && checkEqual(nodeA.right, nodeB.right);
        }else{
            return false;
        }
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月27日下午8:28

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 判断 B 树是否是 A 树的子树或本身
        if (A == null || B == null) {
            return false;
        }

        // 判断 B 是否是 A 的本身，或者 B 是 A 的左子树；或 B 是 A 的右子树。
        return compare(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

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

        // 判断 A 和 B 的子结构是否相同
        return compare(A.left, B.left) && compare(A.right, B.right);
    }
}

思路：判断树 B 是否是树 A 的子结构：树 B 是否和树 A 本身相同或者树 B 是否是树 A 的左子树或右子树的子结构。并且递归的比较 A 和 B 的左子树和右子树是否相同。
时间复杂度：O(n)，需要遍历整个 B 树的节点。
空间复杂度：O(logn)（平均情况）或 O(n)（最坏情况），递归调用栈的深度取决于树的高度。

0 赞同 0 条回复

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

共以下 22 个回答

要么A,B匹配上，要么B与A的子结构匹配。两个递归

# 回答此问题取消回复

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

共以下 22 个回答

要么A,B匹配上，要么B与A的子结构匹配。两个递归

# 回答此问题 取消回复

# 回答此问题取消回复