英文:
Finding the number of nodes at a given depth in a tree
问题
我对于为什么我的递归方法在解决一个问题时不起作用有一点困惑。这是一个用于计算二叉搜索树中给定深度上节点数量的方法。我已经获得了测试用例，但是在一个树的测试用例中，我遇到了一个问题，我在同一棵树的一个深度上得到了正确的答案，但在另一个深度上得到了错误的答案。我困惑于为什么我会得到两个不同的答案，即使这两个答案都是错误的。我的代码和测试代码如下所示。
树的结构：
D
/ \
B F （对于此深度获得正确的输出）（深度 1，节点数量为 2）
/ \ / \
A C E G （在此深度获得不正确的答案）（深度 2，节点数量为 4 但获得了 1）
节点定义代码：
public class simpleBST<Key extends Comparable<Key>, Value> {
private Node root; // BST 的根节点
static boolean verbose = true; // 设置为 false 以抑制正面的测试结果
private class Node {
private Key key; // 键值
private Value val; // 关联的数据
private Node left, right; // 左右子树
public Node(Key key, Value val) {
this.key = key;
this.val = val;
}
}
}
我的代码：
public int numNodesAtDepth(int d) {
return numNodesAtDepthHelper(root, d, 0);
}
public int numNodesAtDepthHelper(Node temp, int d, int cdepth) {
if (temp == null) {
return 0;
}
if (cdepth == d) {
return 1;
}
return numNodesAtDepthHelper(temp.left, d, cdepth++) + numNodesAtDepthHelper(temp.right, d, cdepth++);
}
测试代码：
testnumNodesAtDepth("DBACFEG", 1, 2);
结果：
testnumNodesAtDepthD: 正确 键值: [ DBACFEG ] 实际: 2
测试代码：
testnumNodesAtDepth("DBACFEG", 2, 4);
结果：
testnumNodesAtDepthD: *错误* 键值: [ DBACFEG ] 期望: 4 实际: 1
测试代码只是创建一个带有给定键的树，并调用方法。我困惑于为什么我的代码在同一棵树上获得了两个不同的答案，以及我如何修复这个错误。
英文:
I'm Having a little bit of trouble understanding why my recursive method for a problem isn't working. Its a method meant to produce the number of nodes at a given depth in a binary search tree. I've been given test cases, and I'm having an issue where for a test case on a tree I am getting the correct answer for one depth but the wrong answer for another depth on the same tree. I'm confused why I'm getting two different answers even is the answer is incorrect. My code and the test code is attached below.
Tree Structure
D
/ \
B F (get correct output for this depth) (depth 1, number of Nodes 2)
/ \ / \
A C E G (incorrect answer at this depth) (depth 2, number of Nodes 4 but getting 1)
Node Definition Code:
public class simpleBST<Key extends Comparable<Key>, Value> {
private Node root; // root of BST
static boolean verbose = true; // set to false to suppress positive test results
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // left and right subtrees
public Node(Key key, Value val) {
this.key = key;
this.val = val;
}
My Code
public int numNodesAtDepth(int d) {
return numNodesAtDepthHelper(root,d,0);
}
public int numNodesAtDepthHelper(Node temp,int d,int cdepth)
{
if(temp==null)
{
return 0;
}
if(cdepth==d)
{
return 1;
}
return numNodesAtDepthHelper(temp.left,d,cdepth++) + numNodesAtDepthHelper(temp.right,d,cdepth++);
}
Test Code
testnumNodesAtDepth("DBACFEG",1, 2);
Result
testnumNodesAtDepthD: Correct Keys: [ DBACFEG ] actual: 2
Test Code
testnumNodesAtDepth("DBACFEG",2, 4);
Result
testnumNodesAtDepthD: Error Keys: [ DBACFEG ] expected: 4 actual: 1
The test code just creates a tree with the keys given and calls the method. With the format testnumNodesAtDepth("Keys"(nodes) to be passed in, depth, number of "keys"(nodes) at that depth);
What I'm confused about is how my code gets two different answers on the same tree and how I could fix this error.
答案1
得分: 1
问题在这里：
return numNodesAtDepthHelper(temp.left,d,cdepth+1) + numNodesAtDepthHelper(temp.right,d,cdepth+1);
当你调用 cdepth++ 时，它会增加 cdepth 的值并返回旧值。因此，如果 cdepth 为 1，上面的代码等同于：
return numNodesAtDepthHelper(temp.left,d,1) + numNodesAtDepthHelper(temp.right,d,2);
解决方案是使用 cdepth + 1 代替 cdepth++。
英文:
The issue is here:
return numNodesAtDepthHelper(temp.left,d,cdepth++) + numNodesAtDepthHelper(temp.right,d,cdepth++);
When you call cdepth++, it increases the value of cdepth and returns the old value. So, if cdepth is 1, the above line is equivalent to:
return numNodesAtDepthHelper(temp.left,d,1) + numNodesAtDepthHelper(temp.right,d,2);
The solution is to use cdepth + 1 instead of cdepth++.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论