英文:
Is the value in the distance function being retained?
问题
我试图找到两个节点之间的距离。
在我的具体情况下，两个节点之间的距离是节点之间的边数。
#include <iostream>
using namespace bhargav;
int distance(TreeNode* root, TreeNode* n1)
{
static int height = -1;
if (root == NULL)
return -1;
if (root == n1)
return ++height;
int left = distance(root->left, n1);
if (left >= 0)
return ++height;
int right = distance(root->right, n1);
if (right >= 0)
return ++height;
return height;
}
int main()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);
std::cout << distance(root->right, root->right->left) << "\n";
std::cout << distance(root->right, root->right->right) << "\n";
}
-
如果我在主函数中调用语句
std::cout << distance(root->right, root->right->left) << "\n"; // 1
我得到1作为输出。 -
如果我调用语句
std::cout << distance(root->right, root->right->right) << "\n"; // 1
在主函数中，我得到1作为输出。 -
但是，如果我调用这两个语句
std::cout << distance(root->right, root->right->left) << "\n"; // 1
std::cout << distance(root->right, root->right->right) << "\n"; // 2
我得到1和2作为输出，我想找出输出变化的根本原因。
英文:
I am trying to find the distance between two nodes.
In my specific case, the distance between two nodes is the no of edges between the nodes.
#include <iostream>
using namespace bhargav;
int distance(TreeNode* root, TreeNode* n1)
{
static int height = -1;
if (root == NULL)
return -1;
if (root == n1)
return ++height;
int left = distance(root->left, n1);
if (left >= 0)
return ++height;
int right = distance(root->right, n1);
if (right >= 0)
return ++height;
return height;
}
int main()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);
std::cout << distance(root->right, root->right->left) << "\n";
std::cout << distance(root->right, root->right->right) << "\n";
}
-
If I call the statement
std::cout << distance(root->right, root->right->left) << "\n"; // 1
in the main function, I get 1 as output. -
If I call the statement
std::cout << distance(root->right, root->right->right) << "\n"; // 1
in the main function, I get 1 as output. -
However f I call both statements
std::cout << distance(root->right, root->right->left) << "\n"; // 1
std::cout << distance(root->right, root->right->right) << "\n"; // 2
I get 1 and 2 as output, I want to find the underlying cause of the change in output.
答案1
得分: 3
一个static局部变量将在所有对函数的调用之间共享。它只会被初始化一次，而且只会初始化一次。你不能调用函数两次并期望函数会再次初始化它。
实际上，从编译器的角度来看，对函数的调用没有任何区别：函数调用就是函数调用就是函数调用... 递归对编译器来说并不是什么重要的事情，编译器不知道也不关心，一切都只是相同的调用。
要解决distance无法多次调用（从"顶层"）的问题，你可以使用一个辅助函数来执行实际的工作，以及一个distance函数，它将height定义为一个普通的非静态变量，对其进行初始化，并将其作为参数传递给辅助函数。
也许可以像这样做：
int distance_helper(TreeNode* root, TreeNode* n1, int& height)
{
// ...
int left = distance_helper(root->left, n1, height);
// ...
}
int distance(TreeNode* root, TreeNode* n1)
{
int height = -1;
return distance_helper(root, n1, height);
}
英文:
A static local variable will be shared between all calls to the function. It's initialized once, and only once. You can't call the function twice and expect the function to initialize it again.
In fact, from the compilers point of view there's really no difference between calls to a function: A function call is a function call is a function call... Recursion is not something the compiler knows or cares about, it's all just the same call.
To solve the problem of distance not being possible to call multiple times (from the "top" level), you can use a helper function to do the actual work, and a distance function which defines height as a normal non-static variable, initializes it, and passes it as an argument to the helper function.
Perhaps something like this:
int distance_helper(TreeNode* root, TreeNode* n1, int& height)
{
// ...
int left = distance_helper(root->left, n1, height);
// ...
}
int distance(TreeNode* root, TreeNode* n1)
{
int height = -1;
return distance_helper(root, n1, height);
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论