设计一个判断二叉树的左右子树是否同构的算法
时间: 2024-05-03 17:21:09 浏览: 98
好的,这个问题我可以尝试回答。判断二叉树的左右子树是否同构的问题可以使用递归来解决。首先需要判断两棵二叉树的根节点是否相同,如果不同,则它们肯定不是同构的。如果根节点相同,那么我们需要比较它们的左子树和右子树是否同构。对于左子树和右子树的比较,可以使用递归的方式进行。具体实现可以参考以下代码:
```
bool isIsomorphic(TreeNode* root1, TreeNode* root2) {
// 两棵树均为空,认为是同构的
if (!root1 && !root2) {
return true;
}
// 两棵树中有一棵为空,认为不是同构的
if (!root1 || !root2) {
return false;
}
// 如果根节点的值不同,认为不是同构的
if (root1->val != root2->val) {
return false;
}
// 判断左子树和右子树是否同构,注意参数的顺序
return (isIsomorphic(root1->left, root2->left) && isIsomorphic(root1->right, root2->right)) ||
(isIsomorphic(root1->left, root2->right) && isIsomorphic(root1->right, root2->left));
}
```
需要注意的是,这个算法的时间复杂度是 O(n^4),因为每次比较子树时都需要遍历整棵子树,但是在实际使用中,这个时间复杂度还是比较高的,可以使用其他方法进行优化。
阅读全文