Subtree of Another Tree
给一个树, 求另外一个树是不是这个树的子树.
先写一个方法判断isSameTree, 然后遍历即可.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s)
return false;
if(isSametree(s, t))
return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSametree(TreeNode* s, TreeNode* t) {
if (!s && !t)
return true;
if(!s || !t)
return false;
if (s->val != t->val)
return false;
return isSametree(s->left, t->left) && isSametree(s->right, t->right);
}
};