# 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 scould 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.

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s) return false;
if (isSame(s, t)) return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSame(TreeNode* s, TreeNode* t) {
if (!s && !t) return true;
if (!s || !t) return false;
if (s->val != t->val) return false;
return isSame(s->left, t->left) && isSame(s->right, t->right);
}
};
``````

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
ostringstream os1, os2;
serialize(s, os1);
serialize(t, os2);
return os1.str().find(os2.str()) != string::npos;
}
void serialize(TreeNode* node, ostringstream& os) {
if (!node) os << ",#";
else {
os << "," << node->val;
serialize(node->left, os);
serialize(node->right, os);
}
}
};
``````

Most Frequent Subtree Sum

Serialize and Deserialize Binary Tree

Same Tree

https://discuss.leetcode.com/topic/88508/java-solution-tree-traversal

https://discuss.leetcode.com/topic/88491/java-concise-o-n-m-time-o-n-m-space

https://discuss.leetcode.com/topic/88700/easy-o-n-java-solution-using-inorder-and-preorder-traversal

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation