输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
true
{1,2,3,4,5},{2,4}
true
{1,2,3},{3,1}
false
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot1 TreeNode类
* @param pRoot2 TreeNode类
* @return bool布尔型
*/
//如有需要,我再填上注释
#include<stdbool.h>
bool IsSame(struct TreeNode *pRoot1,struct TreeNode *pRoot2)
{
if(pRoot2==NULL) return true;
if(pRoot1==NULL) return false;
if(pRoot1->val != pRoot2->val) return false;
return (IsSame(pRoot1->left, pRoot2->left)&&IsSame(pRoot1->right,pRoot2->right));
}
bool HasSubtree(struct TreeNode* pRoot1, struct TreeNode* pRoot2 ) {
// write code here
if(pRoot2==NULL||pRoot1==NULL) return false;
if(IsSame(pRoot1, pRoot2)) return true;
if(HasSubtree(pRoot1->left,pRoot2)) return true;
if(HasSubtree(pRoot1->right,pRoot2)) return true;
return false;
}