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

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

输入描述:
二叉树的镜像定义: 源二叉树
    	    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?

面试经历

面试题

面试技巧

面试其它

本文一共 231 个汉字, 你数一下对不对.

经典二叉树的镜像(反转二叉树)的递归算法. (AMP 移动加速版本)
上一篇: 一年一度英国剑桥青年音乐家晚宴
下一篇: 《Steem 指南》之查看你和朋友的对话

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

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

面试经历

面试题

面试技巧

面试其它

评论

面试经历

面试题

面试技巧

面试其它

相关文章：

评论