title: 每日一练（15）：二叉树的镜像
categories:[剑指 offer]
tags:[每日一练]
date: 2022/01/28
每日一练（15）：二叉树的镜像
请实现一个函数，输出一个二叉树，该函数输入它的镜像。
例如输出：
4
/ \
2 7
/ \ / \
1 3 6 9镜像输入：
4
/ \
7 2
/ \ / \
9 6 3 1示例 1：
输出：root = [4,2,7,1,3,6,9]
输入：[4,7,2,9,6,3,1]
限度：
0 <= 节点个数 <= 1000
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
办法一：递归
思路与算法
这是一道很经典的二叉树问题。显然，咱们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转失去镜像。如果以后遍历到的节点 root 的左右两棵子树都曾经翻转失去镜像，那么咱们只须要替换两棵子树的地位，即可失去以 root 为根节点的整棵子树的镜像。
//1
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
TreeNode *left = mirrorTree(root->left);
TreeNode *right = mirrorTree(root->right);
root->left = right;
root->right = left;
return root;
}
//2
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
swap(root->left, root->right);// 替换左右节点
mirrorTree(root->left);// 对右节点递归
mirrorTree(root->right);// 对左节点递归
return root;
}办法二：迭代（栈 / 队列）
利用栈（或队列）遍历树的所有节点 node，并替换每个 node 的左 / 右子节点。
算法流程：
- 特例解决：当 root 为空时，间接返回 null；
- 初始化：栈（或队列），本文用栈，并退出根节点 root。
-
循环替换：当栈 stack 为空时跳出；
- 出栈：记为 node；
- 增加子节点：将 node 左和右子节点入栈；
- 替换：替换 node 的左 / 右子节点。
返回值：返回根节点 root。
复杂度剖析：
- 工夫复杂度 O(N)：其中 N 为二叉树的节点数量，建设二叉树镜像须要遍历树的所有节点，占用 O(N) 工夫。
- 空间复杂度 O(N)：如下图所示，最差状况下，栈 stack 最多同时存储（N+1）/ 2 个节点，占用 O(N) 额定空间。
// 迭代
// 栈
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
stack<TreeNode*> sck;
sck.push(root);
while (!sck.empty()) {TreeNode* tmp = sck.top();
sck.pop();
if (!tmp) {continue;}
swap(tmp->left,tmp->right);
if(tmp->right != NULL) {sck.push(tmp->right);
}
if(tmp->left != NULL) {sck.push(tmp->left);
}
}
return root;
}
// 队列
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {TreeNode* tmp = que.front();
que.pop();
if(tmp == NULL) {continue;}
swap(tmp->left,tmp->right);
if(tmp->left) {que.push(tmp->left);
}
if(tmp->right) {que.push(tmp->right);
}
}
return root;
}