java - 计算二叉树中的节点数

Question

我在计算二叉树中的节点时遇到问题。这是一个真正简单的树，如下图所示。

                                (5)
                       (3)-------^-------(7)
                  (2)---^---(6)           ^-------(9)
                       (5)---^---(8)

我添加了 8 个节点，因此应该有 8 个。但是，当我运行代码时，它计数为 7 个节点。我认为它只是计算所有左节点和右节点，而不计算根，但我将节点数设置为 1 以在计算左节点和右节点之前计算根。请参阅下面的代码

private int getNumNodes(Node<E> root){
        numNodes = 1; // starts by counting the root

        // counts the left nodes
        if(root.left != null){
            numNodes += getNumNodes(root.getLeft());
        }

        // counts the right nodes
        if(root.right != null){
            numNodes += getNumNodes(root.getRight());
        }               
    return numNodes;
}

public int getNumNodes(){
    return root == null ? 0 : getNumNodes(root);
}

一定是在某个地方缺少计数，但我不确定它发生在哪里。你们能帮我一下吗？谢谢。

Answer 1

我认为问题在于 numNodes 是一个类成员，而它应该是该方法的局部变量。