递归创建二叉树时parent引用变量值同步变化的原因咨询

你的代码如下：

Node parent;
    private int size;

    public void addNodes() {
        if (size == 0) {
            Node n = new Node(sc.nextInt());
            parent = n;
            root = n;
            size++;
        }

        System.out.println("Does " + parent.data + " have a left node");

        if (sc.nextBoolean()) {
            Node n = new Node(sc.nextInt());
            parent.left = n;
            parent = n;
            addNodes();
        }

        System.out.println("Does " + parent.data + " have a right node?");

        if (sc.nextBoolean()) {
            Node n = new Node(sc.nextInt());
            parent.right = n;
            parent = n;
            addNodes();
        }
    }

核心问题在于：parent是类的成员变量，不是addNodes()方法的局部变量。

成员变量属于整个类的实例，所有对addNodes()的调用（包括递归的每一层）都会共享同一个parent引用。当你在某一层递归里执行parent = n时，是直接修改了这个全局共享的引用指向——后续不管是当前递归的后续代码，还是其他层的递归调用，拿到的parent都会是这个新的对象，自然所有递归调用里的parent值都变了。

举个具体的例子：

1. 创建根节点A，parent指向A。
2. 处理A的左节点，创建节点B，把parent改成B，然后递归调用addNodes()。
3. 在递归的这一层里，所有操作的parent都是B。等递归返回后回到原来的层，此时parent还是指向B，而不是你以为的A——这时候处理A的右节点时，代码会误以为当前parent是B，导致右节点错误挂到B上，完全不符合二叉树的结构。

修复方案 #

把parent改成方法的局部参数，让每一层递归拥有独立的parent引用，这样修改不会影响其他层：

private int size;
private Node root;
// 假设这里有Scanner sc的定义

public void addNodes() {
    if (size == 0) {
        Node n = new Node(sc.nextInt());
        root = n;
        size++;
        addNodes(n); // 传入根节点作为当前层的parent
    }
}

// 重载方法，用局部参数传递parent
private void addNodes(Node parent) {
    System.out.println("Does " + parent.data + " have a left node?");

    if (sc.nextBoolean()) {
        Node n = new Node(sc.nextInt());
        parent.left = n;
        addNodes(n); // 递归传入新节点，不修改全局变量
    }

    System.out.println("Does " + parent.data + " have a right node?");

    if (sc.nextBoolean()) {
        Node n = new Node(sc.nextInt());
        parent.right = n;
        addNodes(n);
    }
}

这样每一层递归的parent都是独立的局部参数，修改只会影响当前递归分支的后续调用，不会干扰其他层的逻辑，就能正确构建二叉树了。

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