【剑指Offer】（树）树的子结构

一时失言乱红尘 2022-03-16 00:57 174阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88_tpId_13_tqId_11170_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

#### 解决方法 ####

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    class Solution { 
    public:
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        { 
            if (!pRoot1 || !pRoot2 || pRoot1->val!=pRoot2->val) return false;
            return (isSameTree(pRoot1,pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2));
        }
        bool isSameTree(TreeNode* p, TreeNode* q){ 
            //判断以P为根结点的子树是否与q具有相同的结构（注意：这里与判断两棵树是否相同有区别，反例：8 8 9 2与8 8 9）
            if (!q) return true;
            if (!p) return false;
            if (p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right)) return true;
            else return false;
        }
    };

[https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88_tpId_13_tqId_11170_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer-树的子结构

树的子结构题目描述　　输入两颗二叉树A，B，判断B是不是A的子结构。解题思路：　　先判断A的根结点是否与B的树根相同，若相同，则遍历B的同时遍历A,判

怼烎@/ 2022年08月04日 13:34/ 0 赞/ 153 阅读

相关剑指Offer | 树的子结构

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

灰太狼/ 2022年05月24日 14:13/ 0 赞/ 159 阅读

相关剑指Offer-树的子结构

这道题题目的思路总结： 1）二叉树B当前节点值等于二叉树A当时节点值，则递归地去匹配B的左子树和A的左子树，B的右子树和A的右子树 2）二叉树B当前节点值不等于二叉树A

╰+哭是因爲堅強的太久メ/ 2022年05月22日 23:36/ 0 赞/ 184 阅读

相关剑指offer:树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） AC C++ Solution: 递归: class

我会带着你远行/ 2022年04月10日 07:56/ 0 赞/ 191 阅读

相关【剑指offer】树的子结构

树的子结构题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） AC代码方法一 /

一时失言乱红尘/ 2022年04月10日 04:20/ 0 赞/ 163 阅读

相关【剑指Offer】（树）树的子结构

题目链接：[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11

一时失言乱红尘/ 2022年03月16日 00:57/ 0 赞/ 175 阅读

相关剑指Offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路：看到树，第一个想法就是肯定会用到递归。判断B是不是A的子

冷不防/ 2022年02月26日 02:24/ 0 赞/ 206 阅读

相关剑指offer|树的子结构

【题目描述】输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）时间限制：1秒空间限制：32768K 热度指数：432114

素颜马尾好姑娘i/ 2022年02月16日 16:11/ 0 赞/ 201 阅读

相关剑指offer-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）算法实现本博客没有写实现思想，但是在算法实现中已经用注释的

客官°小女子只卖身不卖艺/ 2022年02月13日 15:01/ 0 赞/ 230 阅读

相关剑指offer：树的子结构

试题：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）代码：按照正常思维，我们都知道要一个个搜搜树的节点，每到一个节

妖狐艹你老母/ 2021年09月16日 16:26/ 0 赞/ 318 阅读