每日一练（15）（二叉树的镜像）每日一练（15）：二叉树的镜像

title: 每日一练（15）：二叉树的镜像
categories:[剑指offer]
tags:[每日一练]
date: 2022/01/28
每日一练（15）：二叉树的镜像请完成一个函数，输入一个二叉树，该函数输出它的镜像。
【每日一练（15）（二叉树的镜像）】例如输入：

4 /\ 27 /\/\ 1369

镜像输出：

4 /\ 72 /\/\ 9631

示例 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 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 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; }