首页 > 代码库 > 树B是否为树A的子结构

树B是否为树A的子结构

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        if (pRoot1 == NULL) return false;//这一点很重要,要不然if (pRoot1->val == pRoot2->val)会报空指针的错误
        if (pRoot2 == NULL) return false;
        
        bool res = false;
        
        if(pRoot1->val == pRoot2->val){
            res = DoseTree1HasTree2(pRoot1,pRoot2);
        }
        if(!res){
            res = DoseTree1HasTree2(pRoot1->left,pRoot2);
        }
        if(!res){
            res = DoseTree1HasTree2(pRoot1->right,pRoot2);
        }
        return res;
    }
    
   bool DoseTree1HasTree2(TreeNode* tree1, TreeNode* tree2)
    {
        if (tree1 == NULL &&tree2 == NULL) return true;//tree1和tree2都为空
        else if (tree1 == NULL && tree2!=NULL) return false;
        else if (tree1 != NULL && tree2==NULL) return true;
        else 
        {
            if (tree1->val != tree2->val) return false;
            return DoseTree1HasTree2(tree1->left, tree2->left) && DoseTree1HasTree2(tree1->right, tree2->right);
        }
        
    }

树的子结构

树B是否为树A的子结构