Как мне преобразовать рекурсивный алгоритм, который вызывает себя более одного раза?

Question

У меня есть функция, которая вызывает себя 2 раза в своем теле, и я хочу сделать ее нерекурсивной, используя стек.

У меня есть следующее, чтобы найти глубину двоичного дерева.Это работает, но мне нужно преобразовать его в нерекурсивную функцию.Я думал об использовании stack, но эта функция вызывает себя дважды в своем коде, по одному для каждой стороны.Как мне выполнить требование?

Это мой код до сих пор

struct Node{
    int value;
    Node* left;
    Node* right;
};

int depth(const Node* n){
    // 0 if null
    if(n == nullptr) return 0;
    // max(d(left), d(right)) + 1 otherwise
    return max(depth(n->left), depth(n->right)) + 1;
}

int depthNoRecursion(const Node* n){
        std::stack<Node*> s;
        // Do something here...
}

Answer 1

Вы можете сделать это, используя стек пары, который хранит сам узел и текущий уровень, что-то вроде этого

stack<pair<Node*, int>> stk;
stk.push({root, 1});
int mx_depth = 0;
while(stk.size()){
   auto tp = stk.top();
   mx_depth = max(mx_depth, tp.second);
   stk.pop();
   if(tp.first->left != nullptr)
      stk.push({tp.first->left, tp.second + 1});
  if(tp.first->right != nullptr)
      stk.push({tp.first->right, tp.second + 1});
}