计算二叉树中的节点
问题描述:
我在计算二叉树中的节点时遇到了问题。这是一个真正简单的树,如下图所示。计算二叉树中的节点
(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);
}
它必须在某处丢失计数,但我不确定它在哪里发生。你能帮我一下吗?谢谢。
答
我认为问题在于numNodes
是一个类成员,它应该是方法的局部变量。
+0
+1似乎正确,还要注意,如果给出null作为输入,则代码将失败 – 2013-03-15 01:10:11
要求人们发现代码中的错误并不是特别有效。您应该使用调试器(或者添加打印语句)来分析问题,追踪程序的进度,并将其与预期发生的情况进行比较。只要两者发生分歧,那么你就发现了你的问题。 (然后如果有必要,你应该构造一个[最小测试用例](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