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

本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• Java
• C#

给定二叉树, 请检查二叉树是否包含大小为2或更大的重复子树。

注意：两个相同的叶子节点不被视为叶子节点的子树大小为1。

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

询问：Google面试

推荐：请在"实践首先, 在继续解决方案之前。

带有重复子树的树[以蓝色椭圆突出显示]

[方法1]

一个简单的解决方案是, 我们选择树的每个节点, 然后尝试查找树中是否存在与该子树相同的给定树的任何子树。在这里, 我们可以使用下面的帖子查找子树是否存在于树中的其他任何地方。

检查一个二叉树是否是另一个二叉树的子树

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

一种基于树序列化和哈希的有效解决方案。其思想是将子树序列化为字符串，并将字符串存储在散列表中。一旦发现哈希表中已经存在的序列化树(不是叶子)，就返回true。

下面实现以上想法。

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 "" ; 
    
         subtrees.add(s); 
         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 "" ; 
      
         subtrees.Add(s); 
         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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。