distance函数内变量值是否保留？连续调用输出异常原因排查

问题场景 #

尝试以两个节点间的边数作为节点距离进行计算，编写了对应的C++代码。单独调用计算root->right到root->right->left的距离，或单独调用计算root->right到root->right->right的距离时，输出均为1；但连续调用这两个语句时，输出依次为1和2，需要找出输出变化的根本原因。

问题代码 #

#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";
   
}

根本原因分析 #

问题核心在于distance函数里的**static int height = -1;**语句：

• 被static修饰的变量属于静态存储期，程序运行期间只会初始化一次，后续调用函数时不会重新执行height = -1的初始化操作。
• 第一次调用distance(root->right, root->right->left)时，找到目标节点后，height从-1递增到1，函数返回1。此时静态变量height的值已经固定为1，不会自动重置。
• 第二次调用distance(root->right, root->right->right)时，height的初始值是1而非-1。找到目标节点后，height继续递增到2，因此函数返回2，导致输出异常。

修复建议 #

去掉height的static修饰，改用局部变量配合引用传递来维护递归过程中的距离值，确保每次调用函数时都从初始状态开始计算：

示例修复代码：

#include <iostream>

using namespace bhargav;

void distanceHelper(TreeNode* root, TreeNode* n1, int current, int& result) {
    if (root == nullptr) return;
    if (root == n1) {
        result = current;
        return;
    }
    distanceHelper(root->left, n1, current + 1, result);
    distanceHelper(root->right, n1, current + 1, result);
}

int distance(TreeNode* root, TreeNode* n1) {
    int result = -1;
    distanceHelper(root, n1, 0, result);
    return result;
}

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"; // 输出1
   std::cout << distance(root->right, root->right->right) << "\n"; // 输出1
}

内容的提问来源于stack exchange，提问作者Alpha々 Reaper