1
要求是这样的:给定两颗二叉树A和B,判断B是否是A的子树。
在下面这个例子中可以看到B是A的子树。
想一想该怎样解决这个问题呢?
如果B是A的一颗子树,那么B一定和A的一个颗子树完全一样,因此我们可以实现一个函数isSame来判断两颗二叉树是否完全相同,这个函数非常容易实现:
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); }只需要三行代码就能搞定,该函数非常简单:
如果二叉树a和b都为空,那么显然返回true
否则如果a为空或者b为空,那么这两棵树显然不相同,返回false
如果不满足条件1和2,那么如果a和b根节点的值相同并且其左右子树都一样,那么二叉树a和b是相同的二叉树,返回true
有了isSame函数剩下的就简单啦,我们只需要在遍历二叉树a时不断的调用isSame函数判断是否b是a的子树相同:
同样的,只需要三行代码就能搞定:
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同样的,我们也可以对二叉树计算“md5”值。
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; }将二叉树序列化为字符串后只需要判断字符串b是否是字符串a的子串即可。
审核编辑:刘清
全部0条评论
快来发表一下你的评论吧 !