递归实现二叉树节点计数方法返回0问题求助

嘿，你猜得完全没错！问题的核心就是Integer的不可变性加上Java的参数传递机制导致的，我来给你掰扯清楚，再给你几个可行的修复方案。

为什么你的代码返回始终是0？ #

Java里的参数传递是值传递——对于对象类型来说，传递的是对象引用的副本。而Integer是个不可变类，当你执行cardinalidade = cardinalidade + 1的时候，根本不是修改原来的Integer对象的值，而是创建了一个全新的Integer实例，并且让当前方法里的cardinalidade引用指向这个新对象。但你在contaNos方法里声明的那个原始cardinalidade引用，从头到尾都没变过，一直指向初始值0的那个Integer对象，所以最后返回自然还是0。

修复方案 #

方案1：用可变容器类包裹整数（适合理解原理）

既然Integer不可变，那我们可以自己写一个简单的可变容器类，把int值装进去，这样传递的是容器对象的引用，修改容器里的属性就会影响到原始对象：

public int contaNos(Arvbin r) {
    IntWrapper cardinalidade = new IntWrapper();
    contaNosPrivado(r, cardinalidade);
    return cardinalidade.value;
}

private void contaNosPrivado(Arvbin r, IntWrapper cardinalidade) {
    if (r == null) {
        return;
    }
    cardinalidade.value++; // 直接修改容器里的int值
    contaNosPrivado(r.esq, cardinalidade);
    contaNosPrivado(r.dir, cardinalidade);
}

// 内部可变容器类
private static class IntWrapper {
    int value = 0;
}

方案2：让递归方法返回节点数（推荐，更简洁）

其实统计二叉树节点数的常规递归写法，根本不需要用参数传递计数，直接让递归方法返回当前子树的节点数就好，代码更干净，也避免了可变对象的问题：

public int contaNos(Arvbin r) {
    return contaNosPrivado(r);
}

private int contaNosPrivado(Arvbin r) {
    // 空树节点数为0
    if (r == null) {
        return 0;
    }
    // 当前节点数1 + 左子树节点数 + 右子树节点数
    return 1 + contaNosPrivado(r.esq) + contaNosPrivado(r.dir);
}

这种写法完全符合递归的思想，每一层递归只需要关注当前节点的情况，累加左右子树的结果，逻辑清晰还不容易出错。

内容的提问来源于stack exchange，提问作者João Vitor Sousa