给定两棵二叉树，检查第一棵树是否是第二棵树的子树。树T的子树是一棵树S，由T中的一个节点和T中的所有子节点组成。 根节点对应的子树是整个树；与任何其他节点对应的子树称为适当子树。 例如，在下面的例子中，Tree1是Tree2的子树。
null
Tree1 x / a b c Tree2 z / x e / a b k c
我们讨论过 a O（n） 2. )这个问题的解决方案 .本文讨论了O（n）解。这个想法基于这样一个事实： inorder和preorder/postorder唯一标识二叉树 .树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 areinS[] = {a, c, x, b}preS[] = {x, a, c, b}We can easily figure out that inS[] is a subarray ofinT[] and preS[] is a subarray of preT[].
编辑
The above algorithm doesn't work for cases where a tree is presentin another tree, but not as a subtree. Consider the following example. Tree1 x / a b / c Tree2 x / a b / c dInorder and Preorder traversals of the big tree or Tree2 are.inT[] = {c, a, x, b, d}preT[] = {x, a, c, b, d}Inorder and Preorder traversals of small tree or Tree1 are-inS[] = {c, a, x, b}preS[] = {x, a, c, b}The Tree2 is not a subtree of Tree1, but inS[] and preS[] aresubarrays of inT[] and preT[] respectively.
当我们在顺序和前序遍历中遇到NULL时，可以通过添加一个特殊字符来扩展上述算法以处理此类情况。感谢希瓦姆·戈尔建议延长期限。 下面是上述算法的实现。
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] = ' ' , inS[n] = ' ' ; // 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] = ' ' , preS[n] = ' ' ; // 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] = ' ' ; inS[p.m] = ' ' ; // 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] = ' ' ; preS[p.n] = ' ' ; // 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 |
Python3
MAX = 100 # class for a tree node class Node: def __init__( self ): self .key = ' ' self .left = None self .right = None # A utility function to create a new BST node def newNode(item): temp = Node() temp.key = item 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 def storeInorder(root, i): if (root = = None ): return '$' res = storeInorder(root.left, i) res + = root.key res + = storeInorder(root.right, i) return res # A utility function to store preorder traversal of tree rooted # with root in an array arr[]. Note that i is passed as reference def storePreOrder(root, i): if (root = = None ): return '$' res = root.key res + = storePreOrder(root.left, i) res + = storePreOrder(root.right, i) return res # This function returns true if S is a subtree of T, otherwise false def isSubtree(T, S): # base cases if (S = = None ): return True if (T = = None ): return False # Store Inorder traversals of T and S in inT[0..m-1] # and inS[0..n-1] respectively m = 0 n = 0 inT = storeInorder(T, m) inS = storeInorder(S, n) # If inS[] is not a substring of inT[], return false res = True if inS in inT : res = True else : res = False if (res = = False ): return res # Store Preorder traversals of T and S in preT[0..m-1] # and preS[0..n-1] respectively m = 0 n = 0 preT = storePreOrder(T, m) preS = storePreOrder(S, n) # If preS[] is not a substring of preT[], return false # Else return true if preS in preT: return True else : return False # Driver program to test above function T = newNode( 'a' ) T.left = newNode( 'b' ) T.right = newNode( 'd' ) T.left.left = newNode( 'c' ) T.right.right = newNode( 'e' ) S = newNode( 'a' ) S.left = newNode( 'b' ) S.left.left = newNode( 'c' ) S.right = newNode( 'd' ) if (isSubtree(T, S)): print ( "Yes: S is a subtree of T" ) else : print ( "No: S is NOT a subtree of T" ) # This code is contributed by rj13to. |
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] = ' ' ; inS[p.m] = ' ' ; // 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] = ' ' ; preS[p.n] = ' ' ; // 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字符串匹配算法 . 辅助空间： O（n） 幸亏 阿什维尼·辛格 感谢你提出这种方法。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
