Java二叉树镜像实现求助：两种方法均返回null

先直接戳中最核心的问题：你在main方法里调用的是root.mirrorImage()，但这个方法是TreeNode类里的空实现（直接返回null），而你写的两种正确镜像逻辑是TreeLab类里的静态方法mirrorImage！这就是为什么无论哪种写法都返回null的根本原因。

接下来我们逐一拆解问题并给出修复方案：

1. 修复方法调用错误 #

把main里的display(root.mirrorImage(), 0);改成display(mirrorImage(root), 0);，这样才会调用你在TreeLab中实现的静态镜像方法。

2. 两种镜像实现的细节说明与优化 #

方式1：原地修改原树（镜像后原树结构改变） #

你的逻辑本身是正确的，可以稍微简化代码让可读性更好：

public static TreeNode mirrorImage(TreeNode t) {
    if (t == null) return null;
    // 交换左右子树，递归处理深层节点
    TreeNode temp = t.getLeft();
    t.setLeft(mirrorImage(t.getRight()));
    t.setRight(mirrorImage(temp));
    return t;
}

⚠️ 注意：这种方式会直接修改原二叉树的结构，如果你之后还需要使用原树的话，这种方式就不适用了。

方式2：创建新的镜像树（不修改原树） #

你的逻辑完全正确，不需要改动，只要确保调用正确即可：

public static TreeNode mirrorImage(TreeNode t) {
    if (t == null) return null;
    // 新建节点，左子树绑定原右子树的镜像，右子树绑定原左子树的镜像
    return new TreeNode(t.getValue(), mirrorImage(t.getRight()), mirrorImage(t.getLeft()));
}

这种方式会生成一个全新的镜像树，原树的结构不会被改变，更适合需要保留原树的场景。

3. 修复insert方法的异常问题 #

你怀疑insert方法工作异常是对的，原方法的父节点定位逻辑有问题，导致节点插入到错误位置，甚至可能触发空指针。我们可以修改insert方法的定位逻辑，同时增加空节点的临时创建：

public static void insert(TreeNode t, String s, int pos, int level) {
    TreeNode p = t;
    // 从倒数第二层开始定位父节点
    for (int k = level - 2; k >= 0; k--) {
        if ((pos & (1 << k)) == 0) {
            // 父节点左子树为空时先创建临时节点，避免空指针
            if (p.getLeft() == null) {
                p.setLeft(new TreeNode(""));
            }
            p = p.getLeft();
        } else {
            // 父节点右子树为空时先创建临时节点，避免空指针
            if (p.getRight() == null) {
                p.setRight(new TreeNode(""));
            }
            p = p.getRight();
        }
    }
    // 根据最后一位确定是左还是右子节点
    if ((pos & 1) == 0) {
        p.setLeft(new TreeNode(s, null, null));
    } else {
        p.setRight(new TreeNode(s, null, null));
    }
}

修改后的insert方法会更准确地定位插入位置，同时避免因父节点子树为空导致的空指针问题。

修复后的完整代码 #

public class TreeLab {
    public static void main(String[] args) {
        String s = "XCOMPUTERSCIENCE";
        TreeNode root = new TreeNode("" + s.charAt(1), null, null);
        for(int pos = 2; pos < s.length(); pos++)
            insert(root, "" + s.charAt(pos), pos, (int)(1 + Math.log(pos) / Math.log(2)));
        insert(root, "B", 17, 5);
        insert(root, "A", 18, 5);
        insert(root, "C", 37, 6); //B's right child
        // 打印原树
        System.out.println("Original Tree:");
        display(root, 0);
        // 打印镜像树
        System.out.println("\n\nMirror Image: ");
        display(mirrorImage(root), 0);
        // 如果用方式2，原树不会被修改，可以取消注释验证：
        // System.out.println("\n\nOriginal Tree After Mirror:");
        // display(root, 0);
    }

    public static void insert(TreeNode t, String s, int pos, int level) {
        TreeNode p = t;
        for (int k = level - 2; k >= 0; k--) {
            if ((pos & (1 << k)) == 0) {
                if (p.getLeft() == null) {
                    p.setLeft(new TreeNode(""));
                }
                p = p.getLeft();
            } else {
                if (p.getRight() == null) {
                    p.setRight(new TreeNode(""));
                }
                p = p.getRight();
            }
        }
        if ((pos & 1) == 0) {
            p.setLeft(new TreeNode(s, null, null));
        } else {
            p.setRight(new TreeNode(s, null, null));
        }
    } // end of insert

    // 横向打印树结构
    public static void display(TreeNode t, int level) {
        if(t == null) return;
        display(t.getRight(), level + 1); //先递归右子树
        for(int k = 0; k < level; k++)
            System.out.print("\t");
        System.out.println(t.getValue());
        display(t.getLeft(), level + 1); //再递归左子树
    } // end of display

    // 方式1：原地修改原树的镜像实现
    /*
    public static TreeNode mirrorImage (TreeNode t) {
        if (t == null) return null;
        TreeNode temp = t.getLeft();
        t.setLeft(mirrorImage(t.getRight()));
        t.setRight(mirrorImage(temp));
        return t;
    }
    */

    // 方式2：创建新镜像树的实现（推荐，不修改原树）
    public static TreeNode mirrorImage (TreeNode t) {
        if (t == null) return null;
        else return new TreeNode (t.getValue(), mirrorImage(t.getRight()), mirrorImage(t.getLeft()));
    }
}//end of TreeLab

//TreeNode class
class TreeNode {
    private Object value;
    private TreeNode left, right;
    public TreeNode(Object initValue) {
        value = initValue;
        left = null;
        right = null;
    }
    // 保留原方法但不用它，我们用静态方法实现更灵活
    public TreeNode mirrorImage() {
        return null;
    }
    public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) {
        value = initValue;
        left = initLeft;
        right = initRight;
    }
    public Object getValue() { return value; }
    public TreeNode getLeft() { return left; }
    public TreeNode getRight() { return right; }
    public void setValue(Object theNewValue) { value = theNewValue; }
    public void setLeft(TreeNode theNewLeft) { left = theNewLeft; }
    public void setRight(TreeNode theNewRight) { right = theNewRight; }
}

验证效果 #

运行修复后的代码，你会看到原树和镜像树的正确输出，不会再返回null了。如果使用方式2的镜像实现，原树的结构会保持不变，而方式1会修改原树。

内容的提问来源于stack exchange，提问作者TBallard34