【剑指Offer 19】二叉树的镜像

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

代码如下：

package demo;

public class Test19 {
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    public static void mirrorRecursively(BinaryTreeNode node) {
        if(node != null) {
            // 交换结点左右2个子树
            BinaryTreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            // 对结点的左右子树再进行处理
            mirrorRecursively(node.left);
            mirrorRecursively(node.right);
        }
    }

    /**
     * 中序遍历二叉树
     * @param node
     */
    public static void printTree(BinaryTreeNode node) {
        if(node != null) {
            printTree(node.left);
            printTree(node.right);
            System.out.print(node.value + " ");
        }
    }

测试代码1：

普通二叉树

public static void main(String[] args) {
    /**
     * 1. 普通二叉树
     */
    BinaryTreeNode node = new BinaryTreeNode();
    node.value = 8;
    node.left = new BinaryTreeNode();
    node.left.value = 6;
    node.right = new BinaryTreeNode();
    node.right.value = 10;
    node.left.left = new BinaryTreeNode();
    node.left.left.value = 5;
    node.left.right = new BinaryTreeNode();
    node.left.right.value = 7;
    node.right.left = new BinaryTreeNode();
    node.right.left.value = 9;
    node.right.right = new BinaryTreeNode();
    node.right.right.value = 11;
    System.out.println("普通二叉树是：");
    printTree(node);
    System.out.println();
    System.out.println("普通二叉树的镜像是：");
    mirrorRecursively(node);
    printTree(node);
}

运行结果

测试代码2：

所有结点都没有右子树的二叉树

public static void main(String[] args) {    
    /**
     * 2. 所有结点都没有右子树的二叉树
     */
    BinaryTreeNode node2 = new BinaryTreeNode();
    node2.value = 1;
    node2.left = new BinaryTreeNode();
    node2.left.value = 3;
    node2.left.left = new BinaryTreeNode();
    node2.left.left.value = 5;
    node2.left.left.left = new BinaryTreeNode();
    node2.left.left.left.value = 7;
    node2.left.left.left.left = new BinaryTreeNode();
    node2.left.left.left.left.value = 9;
    System.out.println("所有结点都没有右子树的二叉树是：");
    printTree(node2);
    System.out.println();
    System.out.println("该二叉树的镜像是：");
    mirrorRecursively(node2);
    printTree(node2);
}

运行结果

测试代码3：

所有结点都没有左子树的二叉树

public static void main(String[] args) {        
    /**
     * 3. 所有结点都没有左子树的二叉树
     */
    BinaryTreeNode node3 = new BinaryTreeNode();
    node3.value = 0;
    node3.right = new BinaryTreeNode();
    node3.right.value = 2;
    node3.right.right = new BinaryTreeNode();
    node3.right.right.value = 4;
    node3.right.right.right = new BinaryTreeNode();
    node3.right.right.right.value = 6;
    node3.right.right.right.right = new BinaryTreeNode();
    node3.right.right.right.right.value = 8;
    System.out.println("所有结点都没有左子树的二叉树是：");
    printTree(node3);
    System.out.println();
    System.out.println("该二叉树的镜像是：");
    mirrorRecursively(node3);
    printTree(node3);
}

运行结果

来源：http://blog.csdn.net/derrantcm/article/details/46678173