二叉树镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

分析：

想到递归，对每一个节点有4种情况：

1. 当前节点为空

2. 当前节点不为空，左子树为空

3. 当前节点不为空，右子树为空

4. 当前节点不为空，左右子树都为空

很显然2,3两点可以重合

那么递归退出条件就是1和4

代码

代码如下，测试通过

public static void mirror(TreeNode root) {
        if (root==null)return;
        if (root.left==null && root.right==null) return;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirror(root.left);
        mirror(root.right);
    }

总结

二叉树的递归，遵循以下几步：

1. 找出所有情况

2. 确定退出条件

3. 确定一般递归内容

这一题题目现在看来不难，但是我一开始想偏了，想利用一个辅助函数helper(TreeNode left, TreeNode right)来递归他的左子树和右子树，但是问题在于，每次交换左右子树都变化了，结果就是对于满二叉树可以完成，但是对于不是满二叉树就不行

欢迎大家转载我的博客菜鸡聪。 如果希望交流算法，欢迎联系我， Gmail