温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

剑指offer之面试题18:树的子结构

发布时间:2020-06-23 14:11:14 来源:网络 阅读:427 作者:momo462 栏目:编程语言

题目:

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路:

    //1、遍历二叉树pRoot1,找到和pRoot2根结点相等的结点     //2、在对这个节点进行判断,是否其内部和PRoot2的结构完全相等

代码:

/* struct TreeNode {	int val;	struct TreeNode *left;	struct TreeNode *right;	TreeNode(int x) :	val(x), left(NULL), right(NULL) {	} };*/     class Solution { public:      bool JudgeSub(TreeNode *pRoot1,TreeNode *pRoot2)     {         //一定要先判断PRoot2,在判断proot1         if(pRoot2==NULL)         {             return true;         }          if(pRoot1==NULL)         {             return false;         }         if(pRoot1->val==pRoot2->val)         {             return JudgeSub(pRoot1->left,pRoot2->left)&&JudgeSub(pRoot1->right,pRoot2->right);         }         else         {             return false;         }     }     //1、遍历二叉树pRoot1,找到和pRoot2根结点相等的结点     //2、在对这个节点进行判断,是否其内部和PRoot2的结构完全相等     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)     {         bool result=false;         if(pRoot1!=NULL&&pRoot2!=NULL)         {             if(pRoot1->val==pRoot2->val)             {                 result=JudgeSub(pRoot1,pRoot2);             }             if(!result)             {                 result=HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);             }         }         return result;     } };


向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI