二叉树的镜像

本题选自《剑指offer》第19题
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
审题先明确镜像的定义。

以上图为例，探寻左树如何演变到右树的。

算法是交换左右子树的指针，而不是数值。

private class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

public void mirror(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    swap(root);
    mirror(root.left);
    mirror(root.right);
}

private void swap(BinaryTreeNode root) {
    BinaryTreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
}

算法是递归算法，先序遍历二叉树。

这段代码比书中代码更简洁清晰，原因是空节点的判断都放在了递归边界中完成。

有一个错误是Java初学者易犯的，就是交换左右子树的节点。切记Java方法参数的传递方式是值传递。

// 错误的swap方法
private void swap(BinaryTreeNode p1, BinaryTreeNode p2) {
    BinaryTreeNode tmp = p1;
    p1 = p2;    
    p2 = tmp;
}