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

本文概述

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

给定二叉树, 请检查二叉树是否包含大小为2或更大的重复子树。
注意：两个相同的叶子节点不被视为叶子节点的子树大小为1。

Input :Binary Tree A /\ BC /\\ DEB /\ DE 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=https://www.lsbin.com/data; } }; //This code is contributed by Gaurav Tiwari

// 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 = https://www.lsbin.com/data; } }; // This code is contributed by 29AjayKumar

输出如下：