我在C中有一个二叉搜索树,目前的目标是找到树中的第N个元素。我试图递归地做这件事,但这不是最重要的。我可以访问任何给定节点下的节点数量(包括)。
我试了这段代码:
TreeNode* findNthElement(int N, TreeNode* tree) {
static int count = 0;
printf("nodeCount: %d\nN: %d\nCount: %d\n", tree->nodeCount, N, count);//debug
//null case
if (tree == NULL) {
return NULL;
}
//recursion
if (count <= N) {
findNthElement(N, tree->left);
count++;
if (count == N) {
count = 0;
return tree;
}
findNthElement(N, tree->right);
}
}
这应该是一个递归函数来完成我的任务,但是count
的值总是0,即使它是静态的。我也尝试过在函数外初始化count,并在成功或失败时将其重置为0,但也没有成功。
4条答案
按热度按时间gcuhipw91#
您的代码忽略了递归调用返回的节点,因此,如果递归调用找到了目标节点,调用方并不知道它。此外,在
findNthElement(N, tree->right)
调用之后,不会返回任何内容。同样,你不应该使用静态计数。计数逻辑可以通过 * reduce * 作为N参数传递给递归调用的值来满足。
下面是一个实现:
dauxcl2d2#
这段代码超出了我的知识范围,但是也许
count++
需要在之前递归?因为你在调用递归时没有增加代码中的计数。例如:pzfprimi3#
你根本不需要将count定义为静态的,你可以直接递增参数并递归调用,直到N == count。无论何时调用函数,即使是递归调用,都会在内存堆栈中创建一个新的count变量。
qlzsbp2j4#
为了找到BST中的第n个最小元素,可以应用如下逻辑:
您还可以查看以下资源以获取帮助:
in-order traversal to find nth node
Find k’th smallest node in a Binary Search Tree (BST)
希望这对你有帮助。