Postorder traversal for general graphs without recursion


  • 0
    G

    There are similar questions in the OJ. This question is different for two complications

    1. general graphs that can have cycles
    2. non-recursive
        std::vector<pair<int, bool>> stack;
        std::vector<bool> visited(n, false);
    
        stack.push_back(make_pair(root, false));
        visited[root] = true;
        
        while (!stack.empty()) {
          if (stack.back().second) {
            post_order.push_back(stack.back().first);
            stack.pop_back();
            continue;
          }
          stack.back().second = true;
          for (int y : neighbors[stack.back().first]) {
            if (!visited[y]) {
              stack.push_back(make_pair(y, false));
              visited[y] = true;
            }
          }
        }
    

Log in to reply
 

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