二叉树镜像

题目描述

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

分析:

想到递归,对每一个节点有4种情况:

  1. 当前节点为空
  2. 当前节点不为空,左子树为空
  3. 当前节点不为空,右子树为空
  4. 当前节点不为空,左右子树都为空

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

那么递归退出条件就是14

代码

代码如下,测试通过

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