经典二叉树的镜像(反转二叉树)的递归算法

JustYY.com 小赖子的英国生活和资讯

7 years ago

操作给定的二叉树, 将其变换为源二叉树的镜像. 反转给定的二叉树

输入描述:
二叉树的镜像定义: 源二叉树
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

据说有个工程师去GOOGLE面试就是死在这题上, 不过这题真的不难啊. 有关树的问题多数都可以用递归来完成, 还有其它的一部分则用广度优先. 这题的解题思路就是先递归的镜像左右子树, 然后最后面再交换一下左右节点即可.

这个工程师是很有名的Homebrew的作者, Homebrew是苹果电脑上的软件管理器, 类似ubuntu linux下的 apt-get.

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

阅读 桌面完整版

面试经历

面试题

面试技巧

面试其它

强烈推荐

相关文章：