数据结构和算法面试题：实现一个函数，将一棵二叉树转换为它的镜像。（递归或者非递归实现）
简介：实现一个函数，将一棵二叉树转换为它的镜像。（递归或者非递归实现）
该算法的实现思路如下：
- 对于当前节点，交换其左右子树。
- 递归地对该节点的左右子树进行镜像转换。
下面是使用C++实现将一棵二叉树转换为它的镜像（非递归实现）的代码，并附带详细注释：
#include <iostream> #include <stack> using namespace std; // 定义二叉树结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 将一棵二叉树转换为它的镜像（非递归实现） void mirror_iterative(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> s{{root}}; while (!s.empty()) { TreeNode* node = s.top(); s.pop(); swap(node->left, node->right); // 交换左右子树 if (node->left != nullptr) s.push(node->left); if (node->right != nullptr) s.push(node->right); } } int main() { // 构造一棵二叉树 TreeNode* root = new TreeNode(4); root->left = new TreeNode(2); root->right = new TreeNode(7); root->left->left = new TreeNode(1); root->left->right = new TreeNode(3); root->right->left = new TreeNode(6); root->right->right = new TreeNode(9); // 转换并输出镜像结果 mirror_iterative(root); cout << root->val << endl; // 4 cout << root->left->val << " "; // 7 cout << root->left->left->val << " "; // 9 cout << root->left->right->val << " "; // 6 cout << root->right->val << " "; // 2 cout << root->right->left->val << " "; // 3 cout << root->right->right->val << endl;// 1 return 0; }
下面是同样功能的递归实现代码，也附有详细注释：
#include <iostream> using namespace std; // 定义二叉树结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 将一棵二叉树转换为它的镜像（递归实现） void mirror_recursive(TreeNode* root) { if (root == nullptr) return; swap(root->left, root->right); // 交换当前节点的左右子树 // 递归对左右子树进行镜像操作 mirror_recursive(root->left); mirror_recursive(root->right); } int main() { // 构造一棵二叉树 TreeNode* root = new TreeNode(4); root->left = new TreeNode(2); root->right = new TreeNode(7); root->left->left = new TreeNode(1); root->left->right = new TreeNode(3); root->right->left = new TreeNode(6); root->right->right = new TreeNode(9); // 转换并输出镜像结果 mirror_recursive(root); cout << root->val << endl; // 4 cout << root->left->val << " "; // 7 cout << root->left->left->val << " "; // 9 cout << root->left->right->val << " "; // 6 cout << root->right->val << " "; // 2 cout << root->right->left->val << " "; // 3 cout << root->right->right->val << endl;// 1 return 0; }
这两份代码均以定义二叉树结构的方式构建二叉树。mirror_iterative()函数使用栈进行非递归实现，从而避免了函数调用的栈深，降低了空间复杂度；而mirror_recursive()函数则使用递归实现，代码更加简洁易懂。两个函数的思路都是：对于一个节点，交换其左右子树后，递归地对其左右子树进行同样的操作。
