Блог

Главная - Вопросы по программированию - Сохранение предварительного обхода дерева в векторе

Сохранение предварительного обхода дерева в векторе

#recursion #tree #traversal #tree-traversal

#рекурсия #дерево #обход #обход дерева

Вопрос:

Я пытался сохранить свой предварительный обход в векторе. Сначала я попробовал это.

 vector<int> s;
vector <int> preorder(Node* root)
{
  if(root==NULL)
  return s;  
  s.push_back(root->data);
  preorder(root->left);
  preorder(root->right);
  return s;
}

И это дало мне неправильный ответ, но позже, когда я попробовал это

 void pre(Node* root,vector<int>amp; s)
{
  if(root==NULL)
  return;  
  s.push_back(root->data);
  pre(root->left,s);
  pre(root->right,s);
}
vector <int> preorder(Node* root)
{
 vector<int> s;
 pre(root,s);
 return s;
}

Я получил правильный ответ.Я не понимаю, почему мой первый код выдавал мне WA.
(Как я могу сделать это в одной функции?)

Комментарии:

1. Очищаете ли вы свой вектор s после каждого вызова функции в первом коде? Кажется, вы вызываете несколько раз, но s никогда не очищаетесь.

2. Зачем мне нужно его очищать, я имею в виду, что функция push_back для каждого узла будет выполняться один раз, зачем мне нужно очищать мой вектор? @Suparshva

3. Под несколькими вызовами я имел в виду не в смысле рекурсии. Похоже, вы выполняете несколько предварительных вызовов вне функции с другим root аргументом. Также я предполагаю s , что он является глобальным.

4. Ya s является глобальным. В первом коде у меня была только основная функция, кроме этой. ссылка на ques:practice.geeksforgeeks.org/problems/preorder-traversal/1

5. Тогда, похоже, вы не контролируете код драйвера для своей функции. Код драйвера может вызывать вашу функцию несколько раз.