AcWing 37. 树的子结构

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 37. 树的子结构原题链接简单

作者：

yxc , 2019-01-07 00:54:11 , 所有人可见 , 阅读 9456

64

27

算法

(二叉树，递归) $O(nm)$

代码分为两个部分：

遍历树A中的所有非空节点R；
判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；

对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。

对于第二部分，我们同时从根节点开始遍历两棵子树：

如果树B中的节点为空，则表示当前分支是匹配的，返回true；
如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；

时间复杂度

最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
所以时间复杂度是 $O(nm)$，其中 $n$ 是树A中的节点数， $m$ 是树B中的节点数。

C++ 代码

/**
 * 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 hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot1 || !pRoot2) return false;
        if (isSame(pRoot1, pRoot2)) return true;
        return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    }

    bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot2) return true;
        if (!pRoot1 || pRoot1->val != pRoot2->val) return false;
        return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
    }
};

29 评论

上下求索 2022-03-06 08:22

class Solution {
public:
    bool hasSubtree(TreeNode* a, TreeNode* b) {
        if(!a||!b)return false;
        return helper(a,b)||hasSubtree(a->left,b)||hasSubtree(a->right,b);
    }

    // 判断b是否是以a为根节点的子结构
    bool helper(TreeNode* a,TreeNode* b){
        if(!b)return true;
        if(!a||a->val!=b->val)return false;
        return helper(a->left,b->left)&&helper(a->right,b->right);
    }
};

徐胜虎 2023-04-16 21:28

!pRoot2 一直都是不理解，一直想的是hasSubtree函数调用isSame一直保持pRoot2非空，所以想了想，应该不是考虑这种情况，hasSubtree固定一点，比较用isSame。一直需要注意的是
pRoot1是树 A,pRoot2是数B，pRoot2是不是pRoot1子树，所以hasSubtree固定一点，然后逐点同步比较，pRoot2小的数走完了，pRoot1空了，pRoot2非空说明pRoot2有pRoot1没有的节点，pRoot2空了说明说明，说明一路比较都匹配，然后一种情况是左子树匹配完再去匹配右子树，另一种情况是右子树匹配完返回成功，如果成功，isSame与hasSubtree也都是成功的

wzm_1017 3个月前

谢谢！

阿花_8 2021-10-02 20:46

请问题目不是说空子树不是任何树的子结构，那不是应该if(!pRoot2) return false;吗？麻烦哪位解答一下，谢谢

叫虚 2021-10-03 00:09

这里是isSame的边界，当!p2的时候说明前面都是一致的才能走到这里，要返回true；你说的题意，在代码里是 if (!pRoot1 || !pRoot2) return false;这句话，不矛盾

MagicX 2021-04-26 17:49

if (!pRoot2) return true;这一句应该怎么理解？

tryflow 2021-05-04 13:35

如果树B中的节点为空，则表示当前分支是匹配的，返回true；

KillLemon 2021-01-14 19:51

开始一直没想明白如何匹配，后来看到视频里讲的按照根节点进行类似于字符串的逐一匹配明白过来了，即每次枚举根节点。看看是否有一段完全相同的树

温柔的木头Crystal 2020-12-07 22:56

这个地方我不是特别理解hasSubtree当(!pRoot1 || !pRoot2) return false;而isSame还要继续判断这些是不是空或者是不空，前面不是已经判断过了嘛，为什么到isSame里面还需要判断，去掉这些判断是不通过的。
所以我的问题是两个为什么hasSubtree需要判断
第二个我觉得这个判断是同时进行的，为什么需要在hasSubtree里面判断一次，在isSame里面判断一次。不是很懂，不知道我表达清楚没有