Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
Solution1：遞歸判斷
思路：
Time Complexity: O(m*n) Space Complexity: O(m+n) 遞歸緩存
Solution2：先序列化tree
思路：先序列化tree，再判斷持否contains，如果判斷contains方式用kmp噪猾，則可線性時(shí)間
Time Complexity: O(mn) Space Complexity: O(m+n)
如KMP:
Time Complexity: O(m+n) Space Complexity: O(m+n)
Solution1 Code：
public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
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);
}
}
Solution2 Code：
public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
String spreorder = generatepreorderString(s);
String tpreorder = generatepreorderString(t);
return spreorder.contains(tpreorder);
}
public String generatepreorderString(TreeNode s){
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stacktree = new Stack();
stacktree.push(s);
while(!stacktree.isEmpty()){
TreeNode popelem = stacktree.pop();
if(popelem==null)
sb.append(",#"); // Appending # inorder to handle same values but not subtree cases
else
sb.append(","+popelem.val);
if(popelem!=null){
stacktree.push(popelem.right);
stacktree.push(popelem.left);
}
}
return sb.toString();
}
}
