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

2021年3月11日17:12:12 发表评论 915 次浏览

本文概述

给定两棵二叉树, 请检查第一棵树是否为第二棵树的子树。树T的子树是由S中的节点和T中的所有后代组成的树S。

根节点对应的子树是整个树；与任何其他节点相对应的子树称为适当的子树。

例如, 在以下情况下, Tree1是Tree2的子树。

Tree1
          x 
        /    \
      a       b
       \
        c


        Tree2
              z
            /   \
          x      e
        /    \     \
      a       b      k
       \
        c

推荐：请在"

实践

首先, 在继续解决方案之前。

我们已经讨论过

O(n

2

)解决此问题的方法

。本文讨论了O(n)解。这个想法是基于以下事实：

有序和前序/后序唯一标识二叉树

。如果S的有序遍历和预排序遍历分别是T的有序遍历和预排序遍历的两个子串, 则树S是T的子树。

以下是详细步骤。

1

)找到T的有序遍历和预遍历遍历, 将它们存储在两个辅助数组inT []和preT []中。

2

)找到S的有序遍历和预遍历遍历, 将它们存储在inS []和preS []的两个辅助数组中。

3

)如果inS []是inT []的子数组, 而preS []是preT []的子数组, 则S是T的子树。

在上述算法中, 我们还可以使用后序遍历代替前序。

让我们考虑上面的例子

Inorder and Preorder traversals of the big tree are.
inT[]   =  {a, c, x, b, z, e, k}
preT[]  =  {z, x, a, c, b, e, k}

Inorder and Preorder traversals of small tree are
inS[]  = {a, c, x, b}
preS[] = {x, a, c, b}

We can easily figure out that inS[] is a subarray of
inT[] and preS[] is a subarray of preT[].

编辑

The above algorithm doesn't work for cases where a tree is present
in another tree, but not as a subtree. Consider the following example.

        Tree1
          x 
        /    \
      a       b
     /        
    c         


        Tree2
          x 
        /    \
      a       b
     /         \
    c            d

Inorder and Preorder traversals of the big tree or Tree2 are.

Inorder and Preorder traversals of small tree or Tree1 are

The Tree2 is not a subtree of Tree1, but inS[] and preS[] are
subarrays of inT[] and preT[] respectively.

通过在有序和预序遍历中遇到NULL时添加一个特殊字符, 可以扩展上述算法来处理此类情况。感谢Shivam Goel建议此扩展。

以下是上述算法的实现。

C ++

#include <cstring>
#include <iostream>
using namespace std;
#define MAX 100
 
// Structure of a tree node
struct Node {
     char key;
     struct Node *left, *right;
};
 
// A utility function to create a new BST node
Node* newNode( char item)
{
     Node* temp = new Node;
     temp->key = item;
     temp->left = temp->right = NULL;
     return temp;
}
 
// A utility function to store inorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
void storeInorder(Node* root, char arr[], int & i)
{
     if (root == NULL) {
         arr[i++] = '$' ;
         return ;
     }
     storeInorder(root->left, arr, i);
     arr[i++] = root->key;
     storeInorder(root->right, arr, i);
}
 
// A utility function to store preorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
void storePreOrder(Node* root, char arr[], int & i)
{
     if (root == NULL) {
         arr[i++] = '$' ;
         return ;
     }
     arr[i++] = root->key;
     storePreOrder(root->left, arr, i);
     storePreOrder(root->right, arr, i);
}
 
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(Node* T, Node* S)
{
     /* base cases */
     if (S == NULL)
         return true ;
     if (T == NULL)
         return false ;
 
     // Store Inorder traversals of T and S in inT[0..m-1]
     // and inS[0..n-1] respectively
     int m = 0, n = 0;
     char inT[MAX], inS[MAX];
     storeInorder(T, inT, m);
     storeInorder(S, inS, n);
     inT[m] = '\0' , inS[n] = '\0' ;
 
     // If inS[] is not a substring of inT[], return false
     if ( strstr (inT, inS) == NULL)
         return false ;
 
     // Store Preorder traversals of T and S in preT[0..m-1]
     // and preS[0..n-1] respectively
     m = 0, n = 0;
     char preT[MAX], preS[MAX];
     storePreOrder(T, preT, m);
     storePreOrder(S, preS, n);
     preT[m] = '\0' , preS[n] = '\0' ;
 
     // If preS[] is not a substring of preT[], return false
     // Else return true
     return ( strstr (preT, preS) != NULL);
}
 
// Driver program to test above function
int main()
{
     Node* T = newNode( 'a' );
     T->left = newNode( 'b' );
     T->right = newNode( 'd' );
     T->left->left = newNode( 'c' );
     T->right->right = newNode( 'e' );
 
     Node* S = newNode( 'a' );
     S->left = newNode( 'b' );
     S->left->left = newNode( 'c' );
     S->right = newNode( 'd' );
 
     if (isSubtree(T, S))
         cout << "Yes: S is a subtree of T" ;
     else
         cout << "No: S is NOT a subtree of T" ;
 
     return 0;
}

Java

// Java program to check if binary tree
// is subtree of another binary tree
class Node {
 
     char data;
     Node left, right;
 
     Node( char item)
     {
         data = item;
         left = right = null ;
     }
}
 
class Passing {
 
     int i;
     int m = 0 ;
     int n = 0 ;
}
 
class BinaryTree {
 
     static Node root;
     Passing p = new Passing();
 
     String strstr(String haystack, String needle)
     {
         if (haystack == null || needle == null ) {
             return null ;
         }
         int hLength = haystack.length();
         int nLength = needle.length();
         if (hLength < nLength) {
             return null ;
         }
         if (nLength == 0 ) {
             return haystack;
         }
         for ( int i = 0 ; i <= hLength - nLength; i++) {
             if (haystack.charAt(i) == needle.charAt( 0 )) {
                 int j = 0 ;
                 for (; j < nLength; j++) {
                     if (haystack.charAt(i + j) != needle.charAt(j)) {
                         break ;
                     }
                 }
                 if (j == nLength) {
                     return haystack.substring(i);
                 }
             }
         }
         return null ;
     }
 
     // A utility function to store inorder traversal of tree rooted
     // with root in an array arr[]. Note that i is passed as reference
     void storeInorder(Node node, char arr[], Passing i)
     {
         if (node == null ) {
             arr[i.i++] = '$' ;
             return ;
         }
         storeInorder(node.left, arr, i);
         arr[i.i++] = node.data;
         storeInorder(node.right, arr, i);
     }
 
     // A utility function to store preorder traversal of tree rooted
     // with root in an array arr[]. Note that i is passed as reference
     void storePreOrder(Node node, char arr[], Passing i)
     {
         if (node == null ) {
             arr[i.i++] = '$' ;
             return ;
         }
         arr[i.i++] = node.data;
         storePreOrder(node.left, arr, i);
         storePreOrder(node.right, arr, i);
     }
 
     /* This function returns true if S is a subtree of T, otherwise false */
     boolean isSubtree(Node T, Node S)
     {
         /* base cases */
         if (S == null ) {
             return true ;
         }
         if (T == null ) {
             return false ;
         }
 
         // Store Inorder traversals of T and S in inT[0..m-1]
         // and inS[0..n-1] respectively
         char inT[] = new char [ 100 ];
         String op1 = String.valueOf(inT);
         char inS[] = new char [ 100 ];
         String op2 = String.valueOf(inS);
         storeInorder(T, inT, p);
         storeInorder(S, inS, p);
         inT[p.m] = '\0' ;
         inS[p.m] = '\0' ;
 
         // If inS[] is not a substring of preS[], return false
         if (strstr(op1, op2) != null ) {
             return false ;
         }
 
         // Store Preorder traversals of T and S in inT[0..m-1]
         // and inS[0..n-1] respectively
         p.m = 0 ;
         p.n = 0 ;
         char preT[] = new char [ 100 ];
         char preS[] = new char [ 100 ];
         String op3 = String.valueOf(preT);
         String op4 = String.valueOf(preS);
         storePreOrder(T, preT, p);
         storePreOrder(S, preS, p);
         preT[p.m] = '\0' ;
         preS[p.n] = '\0' ;
 
         // If inS[] is not a substring of preS[], return false
         // Else return true
         return (strstr(op3, op4) != null );
     }
 
     // Driver program to test above functions
     public static void main(String args[])
     {
         BinaryTree tree = new BinaryTree();
         Node T = new Node( 'a' );
         T.left = new Node( 'b' );
         T.right = new Node( 'd' );
         T.left.left = new Node( 'c' );
         T.right.right = new Node( 'e' );
 
         Node S = new Node( 'a' );
         S.left = new Node( 'b' );
         S.right = new Node( 'd' );
         S.left.left = new Node( 'c' );
 
         if (tree.isSubtree(T, S)) {
             System.out.println( "Yes, S is a subtree of T" );
         }
         else {
             System.out.println( "No, S is not a subtree of T" );
         }
     }
}
 
// This code is contributed by Mayank Jaiswal

C#

// C# program to check if binary tree is
// subtree of another binary tree
using System;
 
public class Node {
 
     public char data;
     public Node left, right;
 
     public Node( char item)
     {
         data = item;
         left = right = null ;
     }
}
 
public class Passing {
 
     public int i;
     public int m = 0;
     public int n = 0;
}
 
public class BinaryTree {
 
     static Node root;
     Passing p = new Passing();
 
     String strstr(String haystack, String needle)
     {
         if (haystack == null || needle == null ) {
             return null ;
         }
         int hLength = haystack.Length;
         int nLength = needle.Length;
         if (hLength < nLength) {
             return null ;
         }
         if (nLength == 0) {
             return haystack;
         }
         for ( int i = 0; i <= hLength - nLength; i++) {
             if (haystack[i] == needle[0]) {
                 int j = 0;
                 for (; j < nLength; j++) {
                     if (haystack[i + j] != needle[j]) {
                         break ;
                     }
                 }
                 if (j == nLength) {
                     return haystack.Substring(i);
                 }
             }
         }
         return null ;
     }
 
     // A utility function to store inorder
     // traversal of tree rooted with root in
     // an array arr[]. Note that i is passed as reference
     void storeInorder(Node node, char [] arr, Passing i)
     {
         if (node == null ) {
             arr[i.i++] = '$' ;
             return ;
         }
         storeInorder(node.left, arr, i);
         arr[i.i++] = node.data;
         storeInorder(node.right, arr, i);
     }
 
     // A utility function to store preorder
     // traversal of tree rooted with root in
     // an array arr[]. Note that i is passed as reference
     void storePreOrder(Node node, char [] arr, Passing i)
     {
         if (node == null ) {
             arr[i.i++] = '$' ;
             return ;
         }
         arr[i.i++] = node.data;
         storePreOrder(node.left, arr, i);
         storePreOrder(node.right, arr, i);
     }
 
     /* This function returns true if S
     is a subtree of T, otherwise false */
     bool isSubtree(Node T, Node S)
     {
         /* base cases */
         if (S == null ) {
             return true ;
         }
         if (T == null ) {
             return false ;
         }
 
         // Store Inorder traversals of T and S in inT[0..m-1]
         // and inS[0..n-1] respectively
         char [] inT = new char [100];
         String op1 = String.Join( "" , inT);
         char [] inS = new char [100];
         String op2 = String.Join( "" , inS);
         storeInorder(T, inT, p);
         storeInorder(S, inS, p);
         inT[p.m] = '\0' ;
         inS[p.m] = '\0' ;
 
         // If inS[] is not a substring of preS[], return false
         if (strstr(op1, op2) != null ) {
             return false ;
         }
 
         // Store Preorder traversals of T and S in inT[0..m-1]
         // and inS[0..n-1] respectively
         p.m = 0;
         p.n = 0;
         char [] preT = new char [100];
         char [] preS = new char [100];
         String op3 = String.Join( "" , preT);
         String op4 = String.Join( "" , preS);
         storePreOrder(T, preT, p);
         storePreOrder(S, preS, p);
         preT[p.m] = '\0' ;
         preS[p.n] = '\0' ;
 
         // If inS[] is not a substring of preS[], return false
         // Else return true
         return (strstr(op3, op4) != null );
     }
 
     // Driver program to test above functions
     public static void Main(String[] args)
     {
         BinaryTree tree = new BinaryTree();
         Node T = new Node( 'a' );
         T.left = new Node( 'b' );
         T.right = new Node( 'd' );
         T.left.left = new Node( 'c' );
         T.right.right = new Node( 'e' );
 
         Node S = new Node( 'a' );
         S.left = new Node( 'b' );
         S.right = new Node( 'd' );
         S.left.left = new Node( 'c' );
 
         if (tree.isSubtree(T, S)) {
             Console.WriteLine( "Yes, S is a subtree of T" );
         }
         else {
             Console.WriteLine( "No, S is not a subtree of T" );
         }
     }
}
 
// This code contributed by Rajput-Ji

输出如下： 

No: S is NOT a subtree of T

时间复杂度：

二叉树的有序和预序遍历需要O(n)时间。功能

strstr()

也可以使用O(n)时间来实现

KMP字符串匹配算法

.

辅助空间：

上)

谢谢

阿什维尼·辛格(Ashwini Singh)

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: