在c ++中使用递归返回值

Question

我接受了采访,但我无法回答这个问题.您有一个二叉树,并且您使用in_order将所有节点放入一个数组中,并返回该数组大小的值.我被告知我无法使用辅助函数并为数组计数器添加int i = 0.

我必须使用的递归函数标题是.

      In_order(Struct_Node * node, int *array){

      }

因为我写的是In_order.

      if(node){
      In_order(node->left, array);

//这行是我应该添加元素并返回值的地方,但我不明白该怎么做.这是我的周点,我需要理解这段代码的工作原理比代码更多.

      in_order(node->right,array); 
      }

我实际上并没有写出我在两个In_order语句之间写的内容,但我写的是错误的.

Answer 1

猜测所有遗漏的细节我认为你会做的事情如下:

int In_order(Struct_Node * node, int *array){

   int count = 0;
   if (node->left) {
     count += In_order(node->left, array);
   }
   array[count++] = node->data; // whatever it is you're storing
   if (node->right) {
     count += In_order(node->right, array+count);
   }
   return count;
}

关键是你传递一个更新的指针到RHS递归调用,你的返回值是 1 + LHS return + RHS return

如果你不能使用int作为计数器(这实际上是愚蠢的,因为它是迄今为止表达它的最清晰的方式),你可以这样做:

int In_order(Struct_Node * node, const int *array){
   int *tptr = array;

   if (node->left) {
     tptr += In_order(node->left, array);
   }
   *tptr++ = node->data; // whatever it is you're storing
   if (node->right) {
     tptr += In_order(node->right, tptr);
   }

   return tptr-array;
}

如果你想"有点"疯狂并避免除函数参数之外的任何本地,你可以将返回类型更改为指向数组当前工作端的指针(实际上也是数组的大小)和做:

int *In_order(const Struct_Node * const node, int * const result) {
  return !node ? result :
          In_order(node->right, &(*In_order(node->left, result) = node->value)+1);
}

虽然老实说这是可怕的代码(我甚至不能100%确定它的定义很好!)我真的希望他们不是在寻找这样的解决方案!