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

痛定思痛。 2022-08-22 03:49 113阅读 0赞

**问题描述**：

输入两颗二叉树A和B，判断B是不是A的子结构。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    struct BinaryTreeNode{
    	int date;
    	struct BinaryTreeNode * left;
    	struct BinaryTreeNode * right;
    };
    bool doesTreeFhasTreeSon(struct BinaryTreeNode *TreeF,struct BinaryTreeNode *TreeSon){
    	if(TreeSon==NULL)return true;
    	if(TreeF==NULL)return false;
    	
    	if(TreeF->date!=TreeSon->date)return false;
    	
    	return doesTreeFhasTreeSon(TreeF->left,TreeSon->left) && doesTreeFhasTreeSon(TreeF->right,TreeSon->right);
    	
    }
    
    bool hasSubTree(struct BinaryTreeNode *TreeF,struct BinaryTreeNode *TreeSon){
    	bool result = false;
    	if(TreeF !=NULL && TreeSon !=NULL){
    		if(TreeF->date == TreeSon->date){
    			result = doesTreeFhasTreeSon(TreeF,TreeSon);
    		}
    		if(!result){
    			result = hasSubTree(TreeF->left,TreeSon);
    		}
    		if(!result){
    			result = hasSubTree(TreeF->right,TreeSon);
    		}
    	}
    	return result;	
    }
    
    int main(int argc, char *argv[])
    {
    	struct BinaryTreeNode *Fhead=(struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
    	struct BinaryTreeNode *Sonhead=(struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
    	int i;
    	Fhead->date=0;
    	Fhead->left=(struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
    	Fhead->right=(struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
    	Fhead->left->date=1;
    	Fhead->left->left=NULL;
    	Fhead->left->right=NULL;
    	Fhead->right->date=2;
    	Fhead->right->left=NULL;
    	Fhead->right->right=NULL;
    	Sonhead->date=2;
    	Sonhead->left=NULL;
    	Sonhead->right=NULL;
    	
    	bool b = hasSubTree(Fhead,Sonhead);
    	b==true?printf("true"):printf("false");
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51372186  
作者：WSYW126