Title
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.
这题目就是判断是否为子树问题
O(m*n)
Solution
ac，但看solution好像也没法优化了
//cpp:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool f(TreeNode* s, TreeNode* t){
if(!s&&!t)
return true;
else if(s&&!t)
return false;
else if(!s&&t)
return false;
else if(s->val!=t->val)
return false;
return f(s->left,t->left)&&f(s->right,t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s){
return false;
}
return f(s,t)||isSubtree(s->left,t)||isSubtree(s->right,t);
}
};