本文转载请联系程序员钱宇公众号。Leetcode:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof"GitHub:https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_21_mirrorTree/Solution.java二叉树的镜像》题目描述：请完成一个函数，输入一棵二叉树，函数输出其镜像。例如输入：4/\27/\/\1369镜像输出：4/\72/\/\9631例1：输入：root=[4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]限制：0<=节点数<=1000分析二叉树图像定义：对于二叉树中的任意节点根，设置其左/右子节点为分别向左和向右；那么二叉树镜像中对应的根节点，其左/右子节点分别为right、left。方法一：递归法根据二叉树镜像的定义，考虑递归遍历(dfs)二叉树，交换每个节点的左/右子节点，生成二叉树的镜像。递归分析：终止条件：当节点根为空时（即超出叶节点），则返回null；递归工作：初始化节点tmp，用于暂存root的左子节点；.打开递归右子节点mirrorTree(root.right)，返回值作为root的左子节点。打开递归左子节点mirrorTree(tmp)，返回值作为root的右子节点。返回值：返回当前节点root；《Q：为什么要暂存root的左子节点？A：递归右子节点“root.left=mirrorTree(root.right);”执行后，root.left的值已经存在了发生变化，此时递归的左子节点mirrorTree(root.left)就会出现问题。复杂度分析：时间复杂度0(N)：其中N为二叉树的节点数，构建二叉树镜像需要遍历树的所有节点，耗时O(N)。空间复杂度O(N)：在最坏情况下（二叉树退化为链表时），系统在递归时需要使用O(N)大小的栈空间。packagecom.nateshao.sword_offer.topic_21_mirrorTree;importjava.util.Stack;/***@dateCreatedby邵通杰on2021/11/2422:48*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：剑指Offer27.二叉树镜像*/publicclassSolution{/***递归**@paramroot*@return*/publicTreeNodemirrorTree(TreeNoderoot){if(root==null)returnnull;TreeNodenode=root.left;root.left=mirrorTree(root.right);root.right=mirrorTree(node);返回根；}/***方案一：递归，时间复杂度：O(n)，空间复杂度：O(n)**@paramroot*@return*/publicbooleanisSymmetric(TreeNoderoot){if(root==null)returntrue;returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleftNode,TreeNoderightNode){if(leftNode==null&&rightNode==null)returntrue;if(leftNode==null||rightNode==null)returnfalse;returnleftNode.val==rightNode.val&&isMirror(leftNode.left,rightNode.right)&&isMirror(leftNode.right,rightNode.left);}publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}}方法二：辅助栈（或队列）利用栈（或队列）遍历树的所有节点，交换每个节点的左/右子节点节点。处理：特例处理：当root为空时，直接返回null；初始化：栈（或队列），本文使用栈，并添加根节点root。循环交换：栈为控制时跳出；弹出：记录为节点；添加子节点：将node的左右子节点压入栈中；交换：交换节点的左右子节点。返回值：返回根节点root。复杂度分析：时间复杂度0(N)：其中N为二叉树的节点数，构建二叉树镜像需要遍历树的所有节点，耗时O(N)。空间复杂度O(N)：如下图所示，在最坏的情况下，栈最多可以同时存储N+1/2个节点，占用O(N)的额外空间。packagecom.nateshao.sword_offer.topic_21_mirrorTree;importjava.util.Stack;/***@dateCreatedby邵通杰on2021/11/2422:48*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：剑指Offer27.二叉树镜像*/publicclassSolution{/***stack**@paramroot*@return*/publicTreeNodemirrorTree1(TreeNoderoot){if(root==null)returnnull;Stack
