剑指 Offer 27. 二叉树的镜像 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:01
浏览次数:4
分类:技术文章
本文共 1706 字,大约阅读时间需要 5 分钟。
题目难度: 简单
今天继续更新剑指 offer 系列, 这道题的递归做法很容易想到, 这里额外提供一种迭代方法帮助大家拓展思路
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4 / \ 2 7 / \ / \1 3 6 9
镜像输出:
4 / \ 7 2 / \ / \9 6 3 1
0 <= 节点个数 <= 1000
题目样例
示例
输入
root = [4,2,7,1,3,6,9]
输出
[4,7,2,9,6,3,1]
题目思考
- 如果限制只能用递归或者迭代, 如何解决?
解决方案
方案 1
思路
- 要得到镜像, 如果我们已经得到了当前节点两个子节点各自的镜像, 那么只需要交换子节点位置即可, 这就自然引出了递归的思路, 将大问题化为小问题来解决
- 首先定义递归出口
- 如果节点为空, 其镜像也为空
- 然后写递归内部调用逻辑
- 先得到当前节点的两个子节点递归调用后的结果 left 和 right, 此时 left 就是左子树的镜像, 而 right 就是右子树的镜像
- 然后将当前节点的 left 指向 right, right 指向 left 即可
复杂度
- 时间复杂度
O(N)
- 所有节点只需要遍历一遍
- 空间复杂度
O(N)
- 递归栈的消耗
代码
class Solution: def mirrorTree(self, root: TreeNode) -> TreeNode: # 方法1: 递归交换左右子节点 if not root: return root left, right = self.mirrorTree(root.left), self.mirrorTree(root.right) root.left = right root.right = left return root
方案 2
思路
- 接下来尝试用迭代的思路来解决
- 重新分析题目并观察例子, 我们可以发现其实镜像说白了就是每个节点都交换其直接左右子节点
- 所以我们如果能保证每个节点都恰好交换其子节点一次, 那么操作结束后得到的树就是镜像
- 一个很自然的想法就是类似 BFS 的思路, 使用一个队列存储当前访问到的节点
- 然后对于当前节点, 交换其左右子节点, 然后把非空子节点加入队列等待后面的交换即可
复杂度
- 时间复杂度
O(N)
- 所有节点只需要遍历一遍
- 空间复杂度
O(N)
- 辅助队列需要存 N 个节点
代码
class Solution: def mirrorTree(self, root: TreeNode) -> TreeNode: # 方法2: 迭代, 使用一个队列存储当前的节点 if not root: return None q = [root] for node in q: # 交换当前节点的左右子节点 node.left, node.right = node.right, node.left # 如果子节点不为空的话, 将其加入队列, 等待后续处理 if node.left: q.append(node.left) if node.right: q.append(node.right) # 最终镜像的根节点仍为roott return root
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107235791 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月10日 06时26分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
DIY一只机器狗需要多少钱?最低仅900美元,斯坦福大学出品,代码已开源
2019-04-29
项目是如何死掉的?太过真实!
2019-04-29
卧槽!高清看片网站!!!
2019-04-29
电子专业毕业后,到底能做什么?
2019-04-29
一文通吃所有整流滤波电路
2019-04-29
线上课程推荐 | 计算机方向:无人驾驶中的环境感知
2019-04-29
自行车实现无人驾驶,背后究竟有何“天机”?
2019-04-29
C语言 | 常见数据转化函数
2019-04-29
这届清华学生太难了!C++作业难到上热搜!
2019-04-29
攻城狮危险:波士顿动力机器狗去福特当工程师了!
2019-04-29
突发!华为海思/高通/联发科等50家公司源代码泄露
2019-04-29
程序员崩溃的40个瞬间!(动图)
2019-04-29
为什么中国开发不出流行的操作系统和编程语言?
2019-04-29
你用啥不好?非要用0.1uF电容?
2019-04-29
来,拆一堆芯片看看!
2019-04-29
别和示波器那么陌生,否则你输定了!
2019-04-29
想要学习人工智能?推荐你一条完整的学习路径!
2019-04-29
关于CPU的12个硬核干货!
2019-04-29
为什么要做电路保护,电路保护的意义是什么?
2019-04-29
哪些元器件最容易引发电路故障?
2019-04-29