判断二叉树对称性：递归与迭代解法

"这篇内容主要讨论了如何检查一棵二叉树是否是对称的，即镜像对称。问题来源于LeetCode的一个题目，题号为‘ symmetric tree ’。提供了两种解法，分别是C语言的递归法和C++的迭代法。" 在计算机科学中，特别是数据结构与算法领域，二叉树是一种重要的数据结构。二叉树由节点组成，每个节点包含一个值以及指向左子节点和右子节点的指针。对称二叉树是指如果一棵二叉树的左子树和右子树在结构上是对称的，即它们的镜像，那么这棵树就是对称的。例如，一个对称二叉树可能如下所示： ``` 1 / \ 2 2 / \ / \ 3 4 4 3 ``` 本题的目标是编写函数来判断给定的二叉树是否具有这种对称性质。 **C 递归法** 在递归法中，我们定义一个辅助函数`_ismirror`，它接收两个节点`p`和`q`作为参数，判断它们是否互为镜像。当`p`和`q`都为空时，返回`true`表示空树是镜像的；如果只有一方为空，则返回`false`；如果它们的值相等，我们递归地检查左子树`p->left`和右子树`q->right`，以及右子树`p->right`和左子树`q->left`是否对称。代码如下： ```c bool _ismirror(struct TreeNode* p, struct TreeNode* q) { if ((p == NULL) && (q == NULL)) { return true; } if ((p == NULL) || (q == NULL)) { return false; } if (p->val == q->val) { return _ismirror(p->left, q->right) && _ismirror(p->right, q->left); } return false; } ``` 主函数`isSymmetric`将根节点`root`作为参数传递给`_ismirror`，然后返回结果。 **C++ 迭代法** C++ 的迭代法采用层次遍历（广度优先搜索，BFS）的方式。首先，我们创建一个队列用于存储当前层的节点，同时创建两个队列分别存储左右子节点。在遍历过程中，我们比较同一层的左右子节点是否相等。代码如下： ```cpp bool isSymmetric(TreeNode* root) { if (root == nullptr) return true; queue<TreeNode*> q1, q2; q1.push(root); q2.push(root); while (!q1.empty() && !q2.empty()) { TreeNode* node1 = q1.front(); q1.pop(); TreeNode* node2 = q2.front(); q2.pop(); if (node1->val != node2->val) return false; if (node1->left) { q1.push(node1->left); q2.push(node2->right); } if (node1->right) { q1.push(node1->right); q2.push(node2->left); } } return true; } ``` 这个迭代法的核心思想是，对于每一层的节点，我们比较其左右子节点的值，并在下一层交换左右子节点的位置，以此来检查对称性。 在LeetCode平台上，C语言的递归法在时间和空间效率上表现良好，执行用时8ms，击败了69.91%的C用户，而内存消耗7.9MB，击败了100.00%的C用户。对于C++的迭代法，虽然没有给出具体性能数据，但通常迭代法在空间效率上优于递归法，因为不需要额外的递归栈空间。 总结来说，解决这个问题的关键在于理解二叉树的对称性，并灵活运用递归或迭代的方法进行树的遍历。递归法简洁明了，但可能会有深度限制；迭代法则通常更适用于大规模数据，避免了栈溢出的风险。