突发奇想——1

背景

在题解每日一题-超级骑士-题解中，我们提出了栈来替换函数递归的迭代实现方法，其中使用了迭代替代一个单函数的 dfs 实现性能较优，且易于维护。在今天，我在改自己代码的时候想到一个问题，有没有办法实现一个比较泛化的转换模型呢。在思考下，想出以下内容。

猜想

基础思想

对于一个朴素的前序遍历算法，我们可以用递归来如下实现。

// 普通 dfs （前序遍历树）
void dfs(node* cur) {
     if (cur == nullptr) // 结束递归条件
          return;
     print(cur->data); // 打印节点信息
     dfs(cur->lkid);
     dfs(cur->rkid);
}

我们可以知道的是，对于前序遍历，它输出的顺序是，中 $\to$ 左 $\to$ 右。若我们需要栈来实现函数，理想的出栈顺序应该也是如此，那么对于这个栈，它就应该有以下几种可能

• 栈底 $\to$ 右 $\to$ 左 $\to$ 中
• 栈底 $\to$ 中，栈底 $\to$ 右 $\to$ 左
• 栈底 $\to$ 右 $\to$ 中，栈底 $\to$ 右，栈底 $\to$ 右 $\to$ 左 $\to$ 中
• 栈底 $\to$ 左 $\to$ 中，栈底 $\to$ 右
• 栈底 $\to$ 中，栈底 $\to$ 右，栈底 $\to$ 左

对此，我们只需要实现其中一种即可实现前序遍历。这里我们选择第二种方式是比较合适的。其实现如下

// 迭代普通dfs
void dfs(node* root) {
     std::stack<node*> stack;
     stack.push(root);
     while (not stack.empty()) {
          node* cur = stack.top();
          stack.pop();
          if (cur == nullptr) // 结束递归条件
               continue;
          print(cur->data); // 打印节点信息
          stack.push(cur->rkid); // 右孩子先入栈
          stack.push(cur->lkid); // 左孩子后入栈
     }
}

因此，是不是转换迭代，只需要清楚输出结果和出栈顺序，能够转换就行？我想是吧

进一步的

我们可以将其运用到更难的回溯 dfs 上吗？通常情况下，我们的回溯 dfs 是长这样的。

// 标准回溯 dfs
void dfs(int foo) {
     if (找到答案)
          exit(0);
     for (尝试递归) {
          if (不可递归)
               continue;
          // 否则就是可递归
          打上标记(foo);
          dfs(foo + 1);
          取消标记(foo);
     }
     // 自动返回
}

相比起题解中的 dfs，我们添加了标记回溯，为此，什么时候打标记，什么时候消标记成了难点。可以想到的是，打上标记时，是下一步 dfs 前，而消去标记是在下一步 dfs 结束后。这个过程中的打标记是调用函数前完成的，也是就是在当前函数中完成的，换成栈，也应该是在压栈前完成。又因为循环中会重复标记，所以应该在循环外完成。而消除标记一定伴随着函数栈弹出，所以我们的消除标记应该在弹栈后完成。为此，我们只需要先正常实现无标记回溯的版本，然后在循环外打上标记，弹栈后取消标记即可完成。 以下是一个参考实现

// 迭代回溯 dfs
void dfs(int foo) {
     std::stack<std::pair<int, bool>> stack;
     stack.emplace(foo, false);
     while (not stack.empty()) {
          // 注意是引用，也就是修改回影响栈里面的值
          auto &[bar, 需要回溯] = stack.top();
          if (需要回溯) { // 这里是实现函数结束的自动返回
               stack.pop();
               取消标记(bar);
               continue;
          }
          if (找到答案) // 如果需要多个答案，则和 “需要回溯” 一样
               break;
          打上标记(bar);
          for (尝试递归) {
               if (不可递归)
                    continue;
               // 否则就是可递归
               stack.emplace(bar + 1, false);
          }
          需要回溯 = true; // 记得函数结束会自动返回
     }
}