php - DFS 递归空间使用 PHP

Question

由于数组在 php 中不被视为对象，因此我必须手动引用它们才能递归地填充数组或不断地从递归调用中复制新创建/填充的数组。

" return " myRecursiveFunc() 不是一个选项，因为这会在错误的时间结束函数。

一种方式：参考

public function depthFirstSearchInOrder()
{
   $list = []; //otherwise php screams that only variables can be referenced (inside traverseInOrder) 
   //Otherwise I would have passed an empty [] as second parameter
   return traverseInOrder($this->root, $list);
}

function traverseInOrder($node, &$list)
{
   if ($node->left) {
      traverseInOrder($node->left, $list);
   }

   $list[] = $node->value;

   if ($node->right) {
      traverseInOrder($node->right, $list);
   }

   return $list;
}

第二种方式：创建/复制数组

public function depthFirstSearchInOrder()
{
   return traverseInOrder($this->root);
}

function traverseInOrder($node, $list = [])
{
   if ($node->left) {
      $list = traverseInOrder($node->left, $list);
   }

   $list[] = $node->value;

   if ($node->right) {
      $list = traverseInOrder($node->right, $list);
   }
   return $list;
}

第二种方式不会占用更多空间吗？我正在为每个递归调用创建新数组，然后在 $list 中再次复制。

还是我现在只是困惑？

如果我要穿越这棵树

//            9,
//       4,       20       
//    1,    6,  15   170

使用第二种方式

1. 我会从9开始
2. 向左调用递归（因为 4）
3. 向左调用递归（因为 1）
4. 我用 1 填充我的空数组并返回数组 [1]
5. 我回到了值 4，现在我分配给 $list = [1] （现在是 [1] 的副本而不是引用，对吧？所以数组 [1] 之后仍然存在于某个地方？
6. 我在数组 [1,4] 中推 4 并向右走（因为 6）
7. 我将 6 推入数组 [1,4,6] 并返回此数组 [1,4,6]
8. 我回到了值 4，现在我分配给 $list = [1,4,6] （现在是 [1,4,6] 的副本不是参考，对吧？所以数组 [1,4, 6] 之后还存在于某处吗？

等等等等...

回到我的问题：

第二种方式不是更占空间吗？还是我现在只是困惑？

标签： phparraysrecursionmemory-managementdepth-first-search