判断一颗二叉树是否是另一颗树的子树。

冷不防 2022-04-18 01:56 219阅读 0赞

思路：首先找到值相同的根节点，然后递归判断是否完全相同。  
（方便起见，样例还是建一个二叉搜索树）

#include <bits/stdc++.h>
    using namespace std;
    typedef struct BNode* BTree;
    struct BNode
    {
        
        int data;
        BTree left;
        BTree right;
    };
    
    void Insert(BTree &t,int data){
        
        if(!t){
        
            BTree p=(BTree)malloc(sizeof(BTree));
            p->data=data;
            p->left=NULL;
            p->right=NULL;
            t=p;
        }
        else if(data<t->data)Insert(t->left,data);
        else if(data>=t->data)Insert(t->right,data);
    }
    
    bool Judge(BTree parent,BTree child){
        
        if(child==NULL)return true;
        if(parent==NULL)return false;
        if(parent->data==child->data)return Judge(parent->left,child->left)&&Judge(parent->right,child->right);
        return false;
    }
    bool JudgeTree(BTree parent,BTree child){
        
        if(!parent||!child)return false;
        if(Judge(parent,child))return true;
        return Judge(parent->left,child)||Judge(parent->right,child);
    }
    int main()
    {
        
        int n,m;
        int a[1001],b[1001];
        cin>>n>>m;
        BTree t=NULL,child=NULL;
        for(int i=0;i<n;i++){
        
            cin>>a[i];
            Insert(t,a[i]);
        }
        for(int i=0;i<m;i++){
        
            cin>>b[i];
            Insert(child,b[i]);
        }
        if(JudgeTree(t,child))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }