操作给定的二叉树, 将其变换为源二叉树的镜像.
输入描述:
二叉树的镜像定义: 源二叉树8 / \ 6 10 / \ / \ 5 7 9 11镜像二叉树
8 / \ 10 6 / \ / \ 11 9 7 5
据说有个工程师去GOOGLE面试就是死在这题上, 不过这题真的不难啊. 有关树的问题多数都可以用递归来完成, 还有其它的一部分则用广度优先. 这题的解题思路就是先递归的镜像左右子树, 然后最后面再交换一下左右节点即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 | public class Solution { public void Mirror(TreeNode root) { if (root == null) return; // 递归镜像左子树 Mirror(root.left); // 递归镜像右子树 Mirror(root.right); // 然后再交换左右子节点 TreeNode t = root.left; root.left = root.right; root.right = t; } } |
public class Solution { public void Mirror(TreeNode root) { if (root == null) return; // 递归镜像左子树 Mirror(root.left); // 递归镜像右子树 Mirror(root.right); // 然后再交换左右子节点 TreeNode t = root.left; root.left = root.right; root.right = t; } }
时间复杂度是O(N) – 因为每个节点都需要被访问常数次. 空间复杂度是 O(N) = O(H) 也就是递归的深度.
英文: How to Mirror a Binary Tree?
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK