二叉树的镜像

题目：

请完成一个函数，输入一棵二叉树，该函数输出它的镜像。二叉树节点的定义如下：

public class BinaryTreeNode {

    public int value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
}

函数效果如下图所示：

分析：

​ 最上面的根节点没有发生变化，把它的左右子节点互换，然后再把左右子节点的子节点互换。即使用递归把节点下的左、右子节点互换，直到没有子节点。

代码：

public class BinaryTreeMirror {

    /**
     * 获取二叉树的镜像
     *
     * @param pRoot 二叉树根节点
     */
    public static void getMirrorTree(BinaryTreeNode pRoot) {
        // 判断根节点是否为空
        if (null == pRoot) {
            return;
        }
        // 左、右子节点都不存在
        if (null == pRoot.left || null == pRoot.right) {
            return;
        }

        // 交换左右子节点
        BinaryTreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;

        // 获取左子树的镜像
        if (null != pRoot.left) {
            getMirrorTree(pRoot.left);
        }

        // 获取右子树的镜像
        if (null != pRoot.right) {
            getMirrorTree(pRoot.right);
        }
    }
}

测试：

public class TestBinaryTreeMirror {

    BinaryTreeNode root1 = new BinaryTreeNode(8);

    @Before
    public void before() {

        BinaryTreeNode nodeA11 = new BinaryTreeNode(8);
        BinaryTreeNode nodeA12 = new BinaryTreeNode(7);
        BinaryTreeNode nodeA21 = new BinaryTreeNode(9);
        BinaryTreeNode nodeA22 = new BinaryTreeNode(2);
        BinaryTreeNode nodeA31 = new BinaryTreeNode(4);
        BinaryTreeNode nodeA32 = new BinaryTreeNode(7);

        buildTree(root1, nodeA11, nodeA12);
        buildTree(nodeA11, nodeA21, nodeA22);
        buildTree(nodeA22, nodeA31, nodeA32);

    }

    private void buildTree(BinaryTreeNode root, BinaryTreeNode left, BinaryTreeNode right) {
        root.left = left;
        root.right =right;
    }

    @Test
    public void test() {
        BinaryTreeMirror.getMirrorTree(root1);
        System.out.println(1);
    }
}