剑指offer之面试题18:树的子结构
题目:
输入两棵二叉树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; } };