树的子结构
一、问题描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
二、算法实现
2.1、Java实现
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
//当Tree1和Tree2都存在的时候，才进行比较。否则直接返回false
if(root1!=null && root2!=null){
//根节点一样，那就以这个根节点为起点，去判断是否包含Tree2
if(root1.val == root2.val){
result=IsSub(root1,root2);
}
//如果不一样，那就去root1的左儿子上去找
if(!result){
result=HasSubtree(root1.left,root2);
}
//如果不一样，root1的左儿子上也没有，那就去root1的右儿子上去找
if(!result){
result=HasSubtree(root1.right,root2);
}
}
return result;
}
public boolean IsSub(TreeNode root1,TreeNode root2){
if(root2==null){
//Tree2已经没有要比较的结点了，也就是Tree2是Tree1的子结构，返回true
return true;
}
if(root1==null){ // 此时root2!=null，也就是Tree2还有要比较的结点，而Tree1却没有
return false;
}
if(root1.val != root2.val){//值不相同也不符合。
return false;
}
return IsSub(root1.left,root2.left)&&IsSub(root1.right,root2.right);//如果都相同，那么，继续比较他们的左右子树是不是也是符合这种关系。
}
}这里面有两个递归，第一个递归HasSubtree是为了在root1中找到root2根节点相同的结点。
第二个递归是比较相同结点值下面的子节点是不是root2是root1的子结构。
第一个函数缩小了比较的范围，第二个才是正式比较是否为子结构。
2.2、C++实现
/*
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 = IsSub(pRoot1,pRoot2);
}
if(!result){
result = HasSubtree(pRoot1->left,pRoot2);
}
if(!result){
result = HasSubtree(pRoot1->right,pRoot2);
}
}
return result;
}
bool IsSub(TreeNode* root1,TreeNode* root2){
if(!root2){
return true;
}
if(!root1){
return false;
}
if(root1->val != root2->val){
return false;
}
return IsSub(root1->left,root2->left)&&IsSub(root1->right,root2->right);
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
