bool isSame(TreeNode* a, TreeNode* b) {
if (a == nullptr && b == nullptr) return true;
else if (a == nullptr || b == nullptr) return false;
else return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == nullptr && subRoot == nullptr) return true;
else if (root == nullptr || subRoot == nullptr) return false;
else return isSame(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
$ md5sum a.c
6004b6a21b274b405a2bd1f1c75a93c7 a.c
void serialize(TreeNode* root, string& str) {
if (root == nullptr) {
str = str + "#";
} else {
str = str + "," + to_string(root->val);
serialize(root->left, str);
serialize(root->right, str);
}
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
string a, b;
serialize(root, a);
serialize(subRoot, b);
return a.find(b)!=string::npos;
}
从这个题目上我们可以看到信息编码的重要作用,这也是一种非常值得掌握的思想,有时对解决问题有四两拨千斤的效果。
END
→点关注,不迷路←
文章引用微信公众号"嵌入式微处理器",如有侵权,请联系管理员删除!