计算二叉树中的节点

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

       (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); 
}

它必须在某处丢失计数，但我不确定它在哪里发生。你能帮我一下吗？谢谢。

来源

2013-03-15 TeddyG

要求人们发现代码中的错误并不是特别有效。您应该使用调试器（或者添加打印语句）来分析问题，追踪程序的进度，并将其与预期发生的情况进行比较。只要两者发生分歧，那么你就发现了你的问题。（然后如果有必要，你应该构造一个[最小测试用例]（http://sscce.org）。） – 2013-03-15 01:07:49

我想知道'close（1/5）'是什么意思。 – 2013-03-15 01:09:31

@jdb不，它应该是一个局部变量而不是类成员 – 2013-03-15 01:10:53

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

来源

2013-03-15 01:08:46

+1似乎正确，还要注意，如果给出null作为输入，则代码将失败 – 2013-03-15 01:10:11

计算二叉树中的节点

回答

相关问题