(C++) Turn ANY Recursion Into Iteration


  • 0
    E

    This is just a very stupid but universal solution to turn ANY recursions into iterations.

    Why it works? Because that is exactly what the underlaying CPU operates when you write recursions! They are just calls, pushes, pops, returns...

    The STEP_X emulates the different returning address feed to EIP register.

    For example, the post-order traversal:

    struct CallStackFrame {
      TreeNode * node;
      int step;
      CallStackFrame(TreeNode * node_, int step_) : node(node_), step(step_) {}
    };
    
    const int STEP_INIT = 0;
    const int STEP_1 = 1;
    const int STEP_2 = 2;
    const int STEP_3 = 3;
    const int STEP_FINAL = 9;
    
    class Solution {
    public:
      vector<int> postorderTraversal(TreeNode* root) {
        vector<int> path;
        stack<CallStackFrame *> frames;
        frames.push(new CallStackFrame(root, STEP_INIT));
        while (!frames.empty()) {
          CallStackFrame * frame = frames.top();
          switch (frame->step) {
            case STEP_INIT:
              if (frame->node == NULL) {
                frame->step = STEP_FINAL;
              } else {
                frame->step = STEP_1;
              }
              break;
            case STEP_1:
              frames.push(new CallStackFrame(frame->node->left, STEP_INIT)); // = function call
              frame->step = STEP_2;
              break;
            case STEP_2:
              frames.push(new CallStackFrame(frame->node->right, STEP_INIT)); // = function call
              frame->step = STEP_3;
              break;
            case STEP_3:
              path.push_back(frame->node->val);
              frame->step = STEP_FINAL;
              break;
            case STEP_FINAL:
              frames.pop();  // = end of function
              delete frame;
              break;
          }
        }
        return path;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.