572. Subtree of Another Tree

时间:2022-06-03 12:55:00

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);
}
};