Problem statement:
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.
Solution:
Two extra functions to solve this problem
void find_node() : find all nodes whose value are equal to the root of t.
bool is_subtree(): find if any start node can for a subtree which is same with t.
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
vector<TreeNode*> node_set;
find_node(s, t, node_set);
for(auto node : node_set){
if(is_subtree(node, t)){
return true;
}
}
return false;
}
private:
void find_node(TreeNode* s, TreeNode* t, vector<TreeNode*>& node_set){
if(s == NULL){
return;
}
if(s->val == t->val){
node_set.push_back(s);
}
find_node(s->left, t, node_set);
find_node(s->right, t, node_set);
return;
}
bool is_subtree(TreeNode* s, TreeNode* t){
if(s == NULL && t == NULL){
return true;
}
if((s != NULL && t == NULL) || (s == NULL && t != NULL) || (s->val != t->val)){
return false;
}
return is_subtree(s->left, t->left) && is_subtree(s->right, t->right);
}
};