力扣 - 剑指 Offer 27. 二叉树的镜像
2021/11/24 6:10:28
本文主要是介绍力扣 - 剑指 Offer 27. 二叉树的镜像,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 27. 二叉树的镜像
思路1(递归)
- 我们可以使用深度优先搜索,先递归到链表的末尾,然后从末尾开始两两交换。就相当于后续遍历而已
- 记得要先保存下来
node.right
节点,因为我们在递归完左边才递归右边,而递归完左边的时候,直接把node.right
的指向修改了,如果事先不保存node.right
节点的话,在递归右边传入的节点是错误的节点,因此得不到正确的答案
代码
class Solution { public TreeNode mirrorTree(TreeNode root) { return dfs(root); } public TreeNode dfs(TreeNode node) { // 为空说明到底了 if (node == null) { return null; } // 先记录right节点 TreeNode right = node.right; // 分别递归左边和右边,将 left 和 right 的指针互相交换 node.right = mirrorTree(node.left); node.left = mirrorTree(right); return node; } }
复杂度分析
- 时间复杂度:\(O(N)\),遍历一遍树的每个节点要花费\(O(N)\)的时间复杂度
- 空间复杂度:\(O(N)\),最坏情况下是一条链表,因此递归需要\(O(N)\)的栈空间
思路2(迭代)
- 使用队列(也可以使用栈,差不多一样)进行存储节点,就是数的层序遍历
- 节点是按顺序入队,因此我们需要做的就是将队头元素出队,然后将他的两个子节点入队,再交换两个子节点的值就可以完成一个子节点左右孩子的交换,重复所有的节点
- 其实就是从树根到树叶将每个子节点都进行交换,最终完成了整个树的交换,形成镜像
代码
class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null) { return null; } // 使用队列存储节点 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // 将子节点入队 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } // 交换左右两个子节点 TreeNode temp = node.left; node.left = node.right; node.right = temp; } return root; } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(N)\),栈最多存储 \(\frac{N + 1}{2}\)个节点
这篇关于力扣 - 剑指 Offer 27. 二叉树的镜像的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现