Check if a binary tree is subtree of another binary tree | GeeksforGeeks
Given two binary trees, check if the first tree is subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.
Solution: Traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/
The idea is based on the fact that inorder and preorder/postorder uniquely identify a binary tree. Tree S is a subtree of T if both inorder and preorder traversals of S are substrings of inorder and preorder traversals of T respectively.
1) Find inorder and preorder traversals of T, store them in two auxiliary arrays inT[] and preT[].
2) Find inorder and preorder traversals of S, store them in two auxiliary arrays inS[] and preS[].
3) If inS[] is a subarray of inT[] and preS[] is a subarray preT[], then S is a subtree of T. Else not.
The above algorithm doesn't work for cases where a tree is present in another tree, but not as a subtree.
The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
Time Complexity: Inorder and Preorder traversals of Binary Tree take O(n) time. The functionstrstr() can also be implemented in O(n) time using KMP string matching algorithm.
http://www.jiuzhang.com/solutions/subtree/
Should use LinkedList<String> or StringBuilder.
public String inOrder(Node root, String i){
if(root!=null){
return inOrder(root.left,i) + " " + root.data + " " +inOrder(root.right,i);
}
return "";
}
public String postOrder(Node root, String i){
if(root!=null){
return postOrder(root.left,i) + " " + postOrder(root.right,i) + " " + root.data;
}
return "";
}
public boolean checkSubtree(Node rootA, Node rootB){
String inOrderA = inOrder(rootA,"");
String inOrderB = inOrder(rootB,"");
String postOrderA = postOrder(rootA,"");
String postOrderB = postOrder(rootB,"");
return (inOrderA.toLowerCase().contains(inOrderB.toLowerCase()) && postOrderA.toLowerCase().contains(postOrderB.toLowerCase()));
}
http://www.codebytes.in/2015/01/checking-if-given-binary-tree-is-sub.html ===>not good solution
1. Traverse T1, find nodes that match the root of T2.
2. For all the nodes that match, check if the trees with those roots are equivalent.
Tl and T2 are two very large binary trees, with Tl much bigger than T2. Create an
algorithm to determine ifT2 is a subtree of Tl.
A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2.
That is, if you cut off the tree at node n, the two trees would be identical.
This approach takes O(n + m) time and O(n + m) space,
boolean containsTree(TreeNode tl, TreeNode t2) {
StringBuilder stringl = new StringBuilder();
StringBuilder string2 = new StringBuilder();
getOrderString(tl, s tringl);
getOrderString(t2, string2);
return stringl.indexOf(string2.toString()) != -1;
}
void getOrderString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append ( "X"); / / Add null indicator
return;
}
sb.append (node.data + " "); / / Add root
getOrderString(node.left, sb); // Add left
getOrderString(node.right, sb); // Add right
}
An alternative approach is to search through the larger tree, Tl. Each time a node in Tl matches the root
ofT2, call match Tree. The match Tree method will compare the two subtrees to see if they are identical.
boolean containsTree(TreeNode tl, TreeNode t2) {
if (t2 == null) return true; // The empty tree is always a subtree
return subTree(tl, t2);
}
boolean subTree(TreeNode rl, TreeNode r2) {
if (rl == null) {
return false; // big tree empty & subtree still not found.
} else if (rl.data == r2.data && matchTree(rl, r2)) {
return true;
}
return subTree(rl.left, r2) || subTree(rl.right, r2);
}
boolean matchTree(TreeNode rl, TreeNode r2) {
if (rl == null && r2 == null) {
return true; // nothing left in the subtree
} else if (rl == null || r2 == null) {
return false; // exactly tree is empty, therefore trees dones't match
} else if (rl.data != r2.data) {
return false; // data doesn't match
} else {
return matchTree(rl.left, r2.left) && matchTree(rl.right, r2.right);
}
}
https://reeestart.wordpress.com/2016/06/14/google-is-subtree/
https://discuss.leetcode.com/topic/18/check-if-a-binary-tree-is-a-subtree-of-another-binary-tree/11
Read full article from Check if a binary tree is subtree of another binary tree | GeeksforGeeks
Given two binary trees, check if the first tree is subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.
Solution: Traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.
static Node root1,root2; /* A utility function to check whether trees with roots as root1 and root2 are identical or not */ boolean areIdentical(Node node1, Node node2) { /* base cases */ if (node1 == null && node2 == null) { return true; } if (node1 == null || node2 == null) { return false; } /* Check if the data of both roots is same and data of left and right subtrees are also same */ return (node1.data == node2.data && areIdentical(node1.left, node2.left) && areIdentical(node1.right, node2.right)); } /* 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; } /* Check the tree with root as current node */ if (areIdentical(T, S)) { return true; } /* If the tree with root as current node doesn't match then try left and right subtrees one by one */ return isSubtree(T.left, S) || isSubtree(T.right, S); }The idea is based on the fact that inorder and preorder/postorder uniquely identify a binary tree. Tree S is a subtree of T if both inorder and preorder traversals of S are substrings of inorder and preorder traversals of T respectively.
1) Find inorder and preorder traversals of T, store them in two auxiliary arrays inT[] and preT[].
2) Find inorder and preorder traversals of S, store them in two auxiliary arrays inS[] and preS[].
3) If inS[] is a subarray of inT[] and preS[] is a subarray preT[], then S is a subtree of T. Else not.
The above algorithm doesn't work for cases where a tree is present in another tree, but not as a subtree.
The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
Time Complexity: Inorder and Preorder traversals of Binary Tree take O(n) time. The functionstrstr() can also be implemented in O(n) time using KMP string matching algorithm.
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.
The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
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); }http://www.jiuzhang.com/solutions/subtree/
public boolean isSubtree(TreeNode T1, TreeNode T2) { if (T2 == null) { return true; } if (T1 == null) { return false; } if (isEqual(T1, T2)) { return true; } if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) { return true; } return false; } private boolean isEqual(TreeNode T1, TreeNode T2) { if (T1 == null || T2 == null) { return T1 == T2; } if (T1.val != T2.val) { return false; } return isEqual(T1.left, T2.left) && isEqual(T1.right, T2.right); }http://lintcode.peqiu.com/content/lintcode/subtree.html
首先是特殊情况的处理，然后是树的遍历，可以用栈或者递归，对于判断两个树是否相等，用递归的方式，用栈的话需要同时入出栈，比较麻烦
bool isSubtree(TreeNode *T1, TreeNode *T2) {
// write your code here
if (!T2) {
return true;
} else if (!T1) { // !T1 && T2
return false;
}
stack tmp;
tmp.push(T1);
while(!tmp.empty()) {
TreeNode* pNode = tmp.top();
if(isSubtreeHelper(pNode, T2))
return true;
tmp.pop();
if(pNode->right)
tmp.push(pNode->right);
if(pNode->left)
tmp.push(pNode->left);
}
return false;
}
bool isSubtreeHelper(TreeNode *T1, TreeNode *T2) {
if (!T1 && !T2) {
return true;
}
if (T1 && T2) {
return T1->val == T2->val &&
isSubtreeHelper(T1->left, T2->left) &&
isSubtreeHelper(T1->right, T2->right);
}
return false;
} Should use LinkedList<String> or StringBuilder.
public String inOrder(Node root, String i){
if(root!=null){
return inOrder(root.left,i) + " " + root.data + " " +inOrder(root.right,i);
}
return "";
}
public String postOrder(Node root, String i){
if(root!=null){
return postOrder(root.left,i) + " " + postOrder(root.right,i) + " " + root.data;
}
return "";
}
public boolean checkSubtree(Node rootA, Node rootB){
String inOrderA = inOrder(rootA,"");
String inOrderB = inOrder(rootB,"");
String postOrderA = postOrder(rootA,"");
String postOrderB = postOrder(rootB,"");
return (inOrderA.toLowerCase().contains(inOrderB.toLowerCase()) && postOrderA.toLowerCase().contains(postOrderB.toLowerCase()));
}
http://www.codebytes.in/2015/01/checking-if-given-binary-tree-is-sub.html ===>not good solution
1. Traverse T1, find nodes that match the root of T2.
2. For all the nodes that match, check if the trees with those roots are equivalent.
private void getIdenticals(Node node, Node B, List<Node> store){ if(node==null) return; if(node.equals(B)) store.add(node); getIdenticals(node.left, B, store); getIdenticals(node.right, B, store); } public boolean isSubtree(Node root, Node B){ if(root == null || B == null)return false; List<Node> possibleNodes = new ArrayList<>(); getIdenticals(root, B, possibleNodes); for(Node n:possibleNodes) if(match(n, B))return true; return false; } private boolean match(Node head, Node B){ if(head==null && B == null)return true; if(head==null || B == null)return false; if(head.equals(B)){ if(match(head.left, B.left) && match(head.right, B.right)) return true; } return false; }
Tl and T2 are two very large binary trees, with Tl much bigger than T2. Create an
algorithm to determine ifT2 is a subtree of Tl.
A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2.
That is, if you cut off the tree at node n, the two trees would be identical.
boolean containsTree(TreeNode tl, TreeNode t2) {
StringBuilder stringl = new StringBuilder();
StringBuilder string2 = new StringBuilder();
getOrderString(tl, s tringl);
getOrderString(t2, string2);
return stringl.indexOf(string2.toString()) != -1;
}
void getOrderString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append ( "X"); / / Add null indicator
return;
}
sb.append (node.data + " "); / / Add root
getOrderString(node.left, sb); // Add left
getOrderString(node.right, sb); // Add right
}
An alternative approach is to search through the larger tree, Tl. Each time a node in Tl matches the root
ofT2, call match Tree. The match Tree method will compare the two subtrees to see if they are identical.
boolean containsTree(TreeNode tl, TreeNode t2) {
if (t2 == null) return true; // The empty tree is always a subtree
return subTree(tl, t2);
}
boolean subTree(TreeNode rl, TreeNode r2) {
if (rl == null) {
return false; // big tree empty & subtree still not found.
} else if (rl.data == r2.data && matchTree(rl, r2)) {
return true;
}
return subTree(rl.left, r2) || subTree(rl.right, r2);
}
boolean matchTree(TreeNode rl, TreeNode r2) {
if (rl == null && r2 == null) {
return true; // nothing left in the subtree
} else if (rl == null || r2 == null) {
return false; // exactly tree is empty, therefore trees dones't match
} else if (rl.data != r2.data) {
return false; // data doesn't match
} else {
return matchTree(rl.left, r2.left) && matchTree(rl.right, r2.right);
}
}
https://reeestart.wordpress.com/2016/06/14/google-is-subtree/
不算难的一道题，一看就是递归。但是注意分析这道题的时间复杂度，不是O(n)喔。如果是递归的做法，应该是O(n^2)。而且也有两种递归方式，一种直接递归找subtree，另一种借助isSame()
[Solution #2]
当然这题也有O(n)的解法，对两个tree的任意两种order traversal做KMP. 不包括level order!!
当然这题也有O(n)的解法，对两个tree的任意两种order traversal做KMP. 不包括level order!!
// O(n^2) time 直接递归class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null) { return true; } if (t == null) { return false; } return dfs(s, t); } private boolean dfs(TreeNode s, TreeNode t) { if (s == null && t == null) { return true; } if (s == null || t == null) { return false; } boolean result = false; if (s.val == t.val) { result |= dfs(s.left, t.left) && dfs(s.right, t.right); } result |= dfs(s, t.left); result |= dfs(s, t.right); return result; }}// O(n^2) time 借助isSame() 来递归class Solution2 { public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null) { return true; } if (t == null) { return false; } if (isSame(s, t)) { return true; } return isSubtree(s, t.left) || isSubtree(s, t.right); } private boolean isSame(TreeNode s, TreeNode t) { if (s == null && t == null) { return true; } if (s == null || t == null) { return false; } if (s.val != t.val) { return false; } return isSame(s.left, t.left) && isSame(s.right, t.right); }}Read full article from Check if a binary tree is subtree of another binary tree | GeeksforGeeks
