DOMJUDGE中AVL树程序报RUN-ERROR求排查（结果正确、运行时长0秒）

我提交了一个AVL树相关程序到DOMjudge，程序功能为计算目标值节点的父节点与其父节点的兄弟节点之和（例如目标值是17时，17的父节点是29，29的兄弟节点是15，结果为29+15）。程序结果正确且运行时长为0秒，但却报RUN-ERROR错误，以下是我的程序代码，求排查问题：

int height(AVLNode *root)
{
      if (root == NULL)
            return 0;
      else
      {
            int lheight = height(root->left);
            int rheight = height(root->right);
            if (lheight > rheight)
                  return (lheight + 1);
            else
                  return (rheight + 1);
      }
}

bool CurrentLevel(AVLNode *root, int level, int val)
{
      if (root == NULL)
            return false;

      if (level == 1)
      {
            if (root->data == val)
            {
                  return true;
            }
      }

      else if (level > 1)
      {
            bool left = CurrentLevel(root->left, level - 1, val);
            bool right = CurrentLevel(root->right, level - 1, val);
            return left || right;
      }
      return false;
}

AVLNode *findGrandparent(AVLNode *root, int val)
{
      if (root == NULL || (root->left == NULL && root->right == NULL))
      {
            return NULL;
      }
      else if ((root->left != NULL && (root->left->left != NULL || root->left->right != NULL) && (root->left->left->data == val || root->left->right->data == val)) || (root->right != NULL && (root->right->left != NULL || root->right->right != NULL) && (root->right->left->data == val || root->right->right->data == val)))
      {
            return root;
      }
      else
      {
            AVLNode *left = findGrandparent(root->left, val);
            if (left != NULL)
            {
                  return left;
            }
            else
            {
                  AVLNode *right = findGrandparent(root->right, val);
                  if (right != NULL)
                  {
                        return right;
                  }
                  else
                  {
                        return NULL;
                  }
            }
      }
}

int count_parent(AVLNode *root, int level, int val)
{
      if (root == NULL || level < 2)
      {
            return 0;
      }

      if (level == 2)
      {
            if (root->left != NULL && root->left->data == val)
            {
                  return root->data;
            }
            else if (root->right != NULL && root->right->data == val)
            {
                  return root->data;
            }
      }

      if (level >= 3)
      {
            AVLNode *grandparent = findGrandparent(root, val);
            if (grandparent != NULL)
            {
                  int left_child = (grandparent->left != NULL) ? grandparent->left->data : 0;
                  int right_child = (grandparent->right != NULL) ? grandparent->right->data : 0;
                  return left_child + right_child;
            }
      }

      int left_sum = count_parent(root->left, level - 1, val);
      int right_sum = count_parent(root->right, level - 1, val);
      return left_sum + right_sum;
}


int LOT(AVL *root, int value)
{
      int h = height(root->_root);
      int i;
      for (i = 1; i <= h; i++)
      {
            if (CurrentLevel(root->_root, i, value))
            {
                 return count_parent(root->_root, i, value);
            }
      }

      return 0;
}

int main()
{
      AVL avlku;
      avl_init(&avlku);

      int n,m,val,srch,x;

      scanf("%d", &n);
      scanf("%d", &m);

      int i;
      for (i = 0; i < n; i++)
      {
            scanf("%d", &val);
            avl_insert(&avlku, val);
      }

      for (i = 0; i < m; i++)
      {
            scanf("%d", &srch);
            x = LOT(&avlku, srch);
            printf("%d\n", x);
      }

      return 0;

}

可能的RUN-ERROR原因分析 #

RUN-ERROR通常由非法内存访问（段错误）、未定义行为导致，结合代码重点排查以下几点：

1. AVL树核心函数的实现问题
   你未提供avl_init和avl_insert的代码，这两个函数是AVL树结构正确性的关键：

   • 如果avl_insert创建新节点时，未将节点的left和right指针初始化为NULL，后续遍历（如height、CurrentLevel函数）访问这些野指针会触发段错误。
   • AVL树的旋转操作（若avl_insert包含平衡逻辑）中，若指针指向错误，会导致树结构混乱，遍历过程中访问无效内存。

2. 边界输入的处理缺失

   • 若测试用例中存在目标节点不存在的情况，虽然代码最终返回0，但需确保CurrentLevel和findGrandparent遍历不存在节点时不会访问非法内存（当前代码已有NULL判断，这部分风险较低）。
   • 若输入n=0（无节点插入），需确保avl_init将_root正确初始化为NULL，否则height函数访问NULL指针会触发段错误。

3. 输入输出的格式问题
   检查代码中printf的格式字符串是否正确，若实际代码中写的是printf("%d ", x);（而非printf("%d\n", x);），会导致字符串未闭合，引发编译或运行时错误。

内容的提问来源于stack exchange，提问作者Fauzan Putra S