本文共 1006 字，大约阅读时间需要 3 分钟。

题目描述

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

解题思路

对于两颗树A和B，要判断B是否为A的子树，则其首先应满足根节点相同，然后再去比较；

如果根节点不同，再用A的左子树与B相比，不满足条件的话再用A的右子树与B相比，还不满足则B不在A中。

对于具体的比较，首先比较根节点，再比较左子树和右子树，当都能够满足的条件的话我们便可以认为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 res=false;        if(pRoot1&&pRoot2){
               if(pRoot1->val==pRoot2->val)res=judge(pRoot1,pRoot2);            if(!res)res=HasSubtree(pRoot1->left,pRoot2);            if(!res)res=HasSubtree(pRoot1->right,pRoot2);        }        return res;    }    bool judge(TreeNode* pRoot1, TreeNode* pRoot2){
           if(!pRoot2)return true;        if(!pRoot1)return false;        if(pRoot1->val!=pRoot2->val)return false;        return judge(pRoot1->left,pRoot2->left)&&               judge(pRoot1->right,pRoot2->right);    }};

运行时间：2ms占用内存：488k

转载地址：https://blog.csdn.net/Jeaten/article/details/108362564 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！