AcWing
  • 首页
  • 题库
  • 题解
    • LeetCode
    • AcWing
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

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

作者: 作者的头像   yxc ,  2019-01-07 00:54:11 ,  阅读 1442


15


3

算法

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

代码分为两个部分:

  1. 遍历树A中的所有非空节点R;
  2. 判断树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);
    }
};

评论列表:


用户头像
punkboy   12天前     回复

闫哥,为啥调换这两句的顺序会报错呃。。。要先判断子树是否为空吗
if (!pRoot2) return true;
if (!pRoot1 || pRoot1->val != pRoot2->val) return false;

用户头像
yxc   9天前     回复

对滴。否则如果pRoot2是空,那么调用pRoot2->val就会越界。


用户头像
adnil8130   1个月前     回复

这个题和字符串匹配那么类似。。不知道有没有类似KMP那样优化成O(m + n)的方法呀。。

用户头像
yxc   1个月前     回复

目前还没想到hh


用户头像
mxyzptlk13   4个月前     回复

大佬能帮我看下代码么 检查了几遍 好像不是拼写错误
https://www.acwing.com/community/content/383/

用户头像
yxc   4个月前     回复

我看到有个老哥给出了解答,解答的还不错,可以参考一下hh 其实就是代码最后应该调用 hasSubtree ,你写成了 isMatch

用户头像
mxyzptlk13   4个月前    回复了 yxc 的评论     回复

多谢多谢!


用户头像
贾云杰Yúnjié_7   10个月前     回复

对于递归一直不太能写好,终止条件,递归过程之类的,,,求教大神!

用户头像
yxc   10个月前     回复

递归的题型种类不多,多练就好

你确定删除吗?

© 2018-2019 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息