求二叉树的镜像

递归

破坏原来的树，把原来的树改为其镜像

1. 如果二叉树为空，则返回空；
2. 如果不为空，则求左子树和右子树的镜像，然后交换左右子树。

    /*** 求二叉树的镜像* @param root* @return*/public TreeNode mirror(TreeNode root){if (root == null){return null;}TreeNode l = mirror(root.left);TreeNode r = mirror(root.right);root.left = r;root.right = l;return root;}

不能破坏原来的树，返回一个新的镜像

1. 如果二叉树为空，则返回空；
2. 如果不为空，则创建一个新的节点，新节点的左右孩子分别等于原右子树和左子树的镜像（这里相当于交换了左右子树）。

    /*** 求二叉树的镜像，不破坏原树* @param root* @return*/public TreeNode mirrorCopy(TreeNode root){if (root == null){return null;}TreeNode newTree = new TreeNode(root.val);newTree.left = mirror(root.right);newTree.right = mirror(root.left);return newTree;}

非递归实现

非递归实现，其实就是遍历二叉树的所有节点，然后交换每个节点的左右子树即可。

这里我们用的是层序遍历的方式：

    /*** 求二叉树的镜像，非递归* @param root*/public void mirror2(TreeNode root){if (root == null){return;}LinkedList<TreeNode> list = new LinkedList();list.add(root);while (!list.isEmpty()){TreeNode node = list.poll();TreeNode tmp = node.left;node.left = node.right;node.right = tmp;if (node.left != null){list.add(node.left);}if (node.right != null){list.add(node.right);}}}