Java二叉搜索树中序遍历返回泛型数组index计数异常问题求解

核心问题有两个：

1. 局部变量遮蔽（Variable Shadowing）
   你定义的inorderTraversal方法第三个形参就叫index，和你声明的类成员变量index同名。在方法内部直接使用index时，Java会优先访问当前方法的局部形参，根本不会用到你定义的类全局计数变量，你以为操作的是全局索引，实际操作的是每次递归传递的局部副本。
2. Java基本类型的值传递特性
   int是基本数据类型，作为参数传递时传的是值的副本，你在方法内执行index++修改的只是当前方法栈帧里的局部变量值，既不会影响上层调用的参数值，也不会修改到类的成员变量。

此外你代码中还存在几个额外的编译/运行问题：

• add方法第一行写的root = arr(data,root);，你定义的递归添加方法名为add，不存在名为arr的方法
• 静态内部类BstNode的构造方法名错写为BstDupNode，和类名不一致，无法编译通过
• main方法实例化对象时写的new BstDup<>()，你定义的类名为Bst，不存在BstDup类

方案1：移除方法的index形参，直接使用类成员变量 #

删掉inorderTraversal的第三个参数，全程操作类成员变量index即可：

public E[] getAllData(E[] template) {
    index = 0;
    inorderTraversal(template, root);
    return template;
}

private void inorderTraversal(E[] template, BstNode<E> startNode) {
    if (startNode != null) {
        inorderTraversal(template,startNode.left);
        template[index++] = startNode.data;
        inorderTraversal(template, startNode.right);
    }
}

方案2：用长度为1的int数组包装index #

如果不想使用类成员变量，可以把index装在长度为1的int数组里，数组是引用类型，修改的是堆内存中的真实值，不会受值传递的影响：

public E[] getAllData(E[] template) {
    int[] index = new int[1];
    inorderTraversal(template, root, index);
    return template;
}

private void inorderTraversal(E[] template, BstNode<E> startNode, int[] index) {
    if (startNode != null) {
        inorderTraversal(template,startNode.left, index);
        template[index[0]++] = startNode.data;
        inorderTraversal(template, startNode.right, index);
    }
}

Java的参数传递只有值传递这一种规则：

• 基本类型（int、long、char等）传递的是实际值的副本，方法内部修改副本完全不会影响外部的原变量
• 引用类型传递的是堆内存地址的副本，修改地址指向的堆内容会同步到外部的原变量，但如果给参数重新赋值新对象，不会影响外部的原变量

你之前的写法同时踩了变量遮蔽和值传递两个坑，所以递归过程中索引值不会正常累加，最终只会写入右子树的节点内容，左子树的节点都没有被正确放到数组里。

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