572 Subtree of Another Tree¶
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:
Given tree t:
Return true, because t has the same structure and node values with a subtree of s.
Example 2: Given tree s:
Given tree t:
Return false.
:::tip
- serialize
-
hashset¶
:::
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (t == null) {
return true;
}
if (s == null) {
return false;
}
Set<String> hashset = new HashSet<>();
String string_s = serialize(s, hashset, true);
String string_t = serialize(t, hashset, false);
return hashset.contains(string_t);
}
private String serialize(TreeNode s, Set<String> hashset, boolean save) {
if (s == null) {
return "";
}
String string = s.val + "," + serialize(s.left, hashset, save) + "," + serialize(s.right, hashset, save);
if (save) {
hashset.add(string);
}
return string;
}
}