# 算法：检查二叉树是否包含大小为2或更大的重复子树

2021年3月20日15:53:22 发表评论 373 次浏览

## 本文概述

``````Input :  Binary Tree
A
/    \
B        C
/   \       \
D     E       B
/  \
D    E
Output : Yes``````

[方法1]

[方法2](有效解决方案)

## C ++

``````// C++ program to find if there is a duplicate
// sub-tree of size 2 or more.
#include<bits/stdc++.h>
using namespace std;

// Separator node
const char MARKER = '\$' ;

// Structure for a binary tree node
struct Node
{
char key;
Node *left, *right;
};

// A utility function to create a new node
Node* newNode( char key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return node;
}

unordered_set<string> subtrees;

// This function returns empty string if tree
// contains a duplicate subtree of size 2 or more.
string dupSubUtil(Node *root)
{
string s = "" ;

// If current node is NULL, return marker
if (root == NULL)
return s + MARKER;

// If left subtree has a duplicate subtree.
string lStr = dupSubUtil(root->left);
if (lStr.compare(s) == 0)
return s;

// Do same for right subtree
string rStr = dupSubUtil(root->right);
if (rStr.compare(s) == 0)
return s;

// Serialize current subtree
s = s + root->key + lStr + rStr;

// If current subtree already exists in hash
// table. [Note that size of a serialized tree
// with single node is 3 as it has two marker
// nodes.
if (s.length() > 3 &&
subtrees.find(s) != subtrees.end())
return "" ;

subtrees.insert(s);

return s;
}

// Driver program to test above functions
int main()
{
Node *root = newNode( 'A' );
root->left = newNode( 'B' );
root->right = newNode( 'C' );
root->left->left = newNode( 'D' );
root->left->right = newNode( 'E' );
root->right->right = newNode( 'B' );
root->right->right->right = newNode( 'E' );
root->right->right->left= newNode( 'D' );

string str = dupSubUtil(root);

(str.compare( "" ) == 0) ? cout << " Yes " :
cout << " No " ;
return 0;
}``````

## Java

``````// Java program to find if there is a duplicate
// sub-tree of size 2 or more.
import java.util.HashSet;
public class Main {

static char MARKER = '\$' ;

// This function returns empty string if tree
// contains a duplicate subtree of size 2 or more.
public static String dupSubUtil(Node root, HashSet<String> subtrees)
{
String s = "" ;

// If current node is NULL, return marker
if (root == null )
return s + MARKER;

// If left subtree has a duplicate subtree.
String lStr = dupSubUtil(root.left, subtrees);
if (lStr.equals(s))
return s;

// Do same for right subtree
String rStr = dupSubUtil(root.right, subtrees);
if (rStr.equals(s))
return s;

// Serialize current subtree
s = s + root.data + lStr + rStr;

// If current subtree already exists in hash
// table. [Note that size of a serialized tree
// with single node is 3 as it has two marker
// nodes.
if (s.length() > 3 && subtrees.contains(s))
return "" ;

return s;
}

//Function to find if the Binary Tree contains duplicate
//subtrees of size 2 or more
public static String dupSub(Node root)
{
HashSet<String> subtrees= new HashSet<>();
return dupSubUtil(root, subtrees);
}

public static void main(String args[])
{
Node root = new Node( 'A' );
root.left = new Node( 'B' );
root.right = new Node( 'C' );
root.left.left = new Node( 'D' );
root.left.right = new Node( 'E' );
root.right.right = new Node( 'B' );
root.right.right.right = new Node( 'E' );
root.right.right.left= new Node( 'D' );
String str = dupSub(root);
if (str.equals( "" ))
System.out.print( " Yes " );
else
System.out.print( " No " );
}
}

// A binary tree Node has data, // pointer to left child
// and a pointer to right child
class Node {
int data;
Node left, right;
Node( int data)
{
this .data=data;
}
};
//This code is contributed by Gaurav Tiwari``````

## C#

``````// C# program to find if there is a duplicate
// sub-tree of size 2 or more.
using System;
using System.Collections.Generic;

class GFG
{

static char MARKER = '\$' ;

// This function returns empty string if tree
// contains a duplicate subtree of size 2 or more.
public static String dupSubUtil(Node root, HashSet<String> subtrees)
{
String s = "" ;

// If current node is NULL, return marker
if (root == null )
return s + MARKER;

// If left subtree has a duplicate subtree.
String lStr = dupSubUtil(root.left, subtrees);
if (lStr.Equals(s))
return s;

// Do same for right subtree
String rStr = dupSubUtil(root.right, subtrees);
if (rStr.Equals(s))
return s;

// Serialize current subtree
s = s + root.data + lStr + rStr;

// If current subtree already exists in hash
// table. [Note that size of a serialized tree
// with single node is 3 as it has two marker
// nodes.
if (s.Length > 3 && subtrees.Contains(s))
return "" ;

return s;
}

// Function to find if the Binary Tree contains
// duplicate subtrees of size 2 or more
public static String dupSub(Node root)
{
HashSet<String> subtrees = new HashSet<String>();
return dupSubUtil(root, subtrees);
}

// Driver code
public static void Main(String []args)
{
Node root = new Node( 'A' );
root.left = new Node( 'B' );
root.right = new Node( 'C' );
root.left.left = new Node( 'D' );
root.left.right = new Node( 'E' );
root.right.right = new Node( 'B' );
root.right.right.right = new Node( 'E' );
root.right.right.left= new Node( 'D' );
String str = dupSub(root);
if (str.Equals( "" ))
Console.Write( " Yes " );
else
Console.Write( " No " );
}
}

// A binary tree Node has data, // pointer to left child
// and a pointer to right child
public class Node
{
public int data;
public Node left, right;
public Node( int data)
{
this .data = data;
}
};

// This code is contributed by 29AjayKumar``````

``Yes``