剑指offer：树的子结构代码实现

迈不过友情╰ 2022-08-04 15:42 121阅读 0赞

题目描述

输入两颗二叉树A，B，判断B是不是A的子结构。

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)
        {
            bool result = false;
    
            if(pRoot1 != NULL && pRoot2 != NULL)
            {
                /* 如果这个节点相同，则判断是否是子树 */
                if(pRoot1->val == pRoot2->val)
                {
                    result = hasTree1IncludeTree2(pRoot1,pRoot2);
                }
    
                /* 如果不是，接下来递归判断左子树 */
                if(result == false)
                {
                    result = HasSubtree(pRoot1->left,pRoot2);
                }
    
                /* 如果不是，接下来递归判断右子树 */
                if(result == false)
                {
                    result = HasSubtree(pRoot1->right,pRoot2);
                }
            }
    
            return result;
        }
    
        /* 判断pRoot2是否是pRoot1的子树 */
        bool hasTree1IncludeTree2(TreeNode* pRoot1, TreeNode* pRoot2)
        {
    
            /* 如果树2为空，则所有都匹配，查找成功 */
            if(pRoot2 == NULL)
            {
                return true;
            }
    
            if(pRoot1 == NULL)
            {
                return false;
            }
    
            if(pRoot1->val != pRoot2->val)
            {
                return false;
            }
    
            return hasTree1IncludeTree2(pRoot1->left,pRoot2->left) && 
                    hasTree1IncludeTree2(pRoot1->right,pRoot2->right);
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer：树的子结构代码实现

题目描述输入两颗二叉树A，B，判断B是不是A的子结构。 struct TreeNode { int val; struct Tre

迈不过友情╰/ 2022年08月04日 15:42/ 0 赞/ 122 阅读

相关剑指Offer | 树的子结构

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

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

相关剑指Offer-树的子结构

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

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

相关剑指offer:树的子结构

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

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

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

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

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

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

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

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

相关剑指Offer-树的子结构

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

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

相关剑指offer|树的子结构

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

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

相关剑指offer-树的子结构

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

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

相关剑指offer：树的子结构

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

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