题解 | #二叉树的镜像#
二叉树的镜像
http://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7
算法思想一：递归
解题思路：
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
解题步骤：
1、特判：如果pRoot为空，返回空
2、交换左右子树
3、把pRoot的左子树放到Mirror中镜像一下
4、把pRoot的右子树放到Mirror中镜像一下
5、返回根节点root
3、把pRoot的左子树放到Mirror中镜像一下
4、把pRoot的右子树放到Mirror中镜像一下
5、返回根节点root
图解：
代码展示：
Python版本
class Solution: def Mirror(self , pRoot ): # write code here if not pRoot: return pRoot # 左右子树交换 pRoot.left, pRoot.right = pRoot.right, pRoot.left # 递归左右子树 self.Mirror(pRoot.left) self.Mirror(pRoot.right) return pRoot复杂度分析：
时间复杂度O(N)：其中 N为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
空间复杂度O(N)：最差情况下（当二叉树退化为链表），递归时系统需使用O(N) 大小的栈空间
算法思想二：辅助栈/队列
解题思路：
主要是利用栈（或队列）遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点
算法流程：
1、特例处理： 当 pRoot为空时，直接返回 null ；
2、初始化： 栈（或队列），本文用栈stack ，并加入根节点 pRoot。
3、循环交换： 当栈 stack 为空时跳出；
3.1、出栈： 记为 node ；
3.2、添加子节点： 将 node 左和右子节点入栈；
3.3、交换： 交换 node 的左 / 右子节点。
4、返回值： 返回根节点 pRoot 。
图解：
1、特例处理： 当 pRoot为空时，直接返回 null ；
2、初始化： 栈（或队列），本文用栈stack ，并加入根节点 pRoot。
3、循环交换： 当栈 stack 为空时跳出；
3.1、出栈： 记为 node ；
3.2、添加子节点： 将 node 左和右子节点入栈；
3.3、交换： 交换 node 的左 / 右子节点。
4、返回值： 返回根节点 pRoot 。
图解：
代码展示：
JAVA版本
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot == null) return null;
// 构建辅助栈
Stack<TreeNode> stack = new Stack<>();
// 根节点入栈
stack.add(pRoot);
while(!stack.isEmpty()) {
// 节点出栈
TreeNode node = stack.pop();
// 根节点的左右子树入栈
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
// 左右子树交换
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return pRoot;
}
} 复杂度分析：
时间复杂度O(N)：其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
空间复杂度O(N)：如下图所示，最差情况下，栈 stackstack 最多同时存储（N + 1）/ 2 个节点，占用 O(N)额外空间。
