经典二叉树的镜像的递归算法


操作给定的二叉树, 将其变换为源二叉树的镜像.
输入描述:
二叉树的镜像定义: 源二叉树

    	    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?

GD Star Rating
loading...
本文一共 194 个汉字, 你数一下对不对.
经典二叉树的镜像的递归算法. (AMP 移动加速版本)
上一篇: 一年一度英国剑桥青年音乐家晚宴
下一篇: 《Steem 指南》之查看你和朋友的对话

扫描二维码,分享本文到微信朋友圈
19470b28b11ca00c7d3017b5ef912ae6 经典二叉树的镜像的递归算法 ACM题解 数据结构与算法

评论