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

本文概述

C ++
Java
C#

给定两棵二叉树, 请检查第一棵树是否为第二棵树的子树。树T的子树是由S中的节点和T中的所有后代组成的树S。
根节点对应的子树是整个树；与任何其他节点相对应的子树称为适当的子树。
例如, 在以下情况下, Tree1是Tree2的子树。

Tree1 x /\ ab \ cTree2 z /\ xe /\\ abk \ 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 /\ ab / cTree2 x /\ ab /\ cdInorder and Preorder traversals of the big tree or Tree2 are.Inorder and Preorder traversals of small tree or Tree1 areThe 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 = https://www.lsbin.com/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# 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 = https://www.lsbin.com/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)
【如何检查一个二叉树是否是另一个二叉树的子树（）】建议这种方法。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。