Algorithm (DFS)

1. Regular DFS works. Just keep track of the builder position and maintain a parent tracker map.
2. We keep two states, prev_move and cur_move, as a reference to the current depth and id as the node id to be inserted. The build behavior is dependent on the order of these two states.
   • if size(prev_move) > size(cur_move), we trim prev_move on the left by one and go up until the two are even.
   • if size(prev_move) = size(cur_move), we assign id to the right child of the current builder node and advance the builder node to its right child.
   • if size(prev_move) < size(cur_move), we assign id to the left child of the current builder node and advancde the builder node to its left child.
3. Note that the root case may be dealt with on the side. We combine the two using optional monad.
4. We have a modularized tokenizer to facilitate the solution.

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F>
recursive(F)->recursive<F>;
auto const rec = [](auto f) { return recursive{std::move(f)}; };

struct tokenizer {
  const string data;
  int cursor;

  tokenizer(const string& str) : data(str), cursor(-1){};

  optional<char> peek() {
    if (cursor + 1 < size(data))
      return {data[cursor + 1]};
    else
      return {};
  };

  char read() { return data[++cursor]; };

  template <typename T, typename std::enable_if_t<std::is_same_v<string, T>>* = nullptr>
  T next() {
    string result{};
    while (peek() and not isdigit(peek().value()))
      result.push_back(read());
    return result;
  }

  template <typename T, typename std::enable_if_t<std::is_same_v<int, T>>* = nullptr>
  T next() {
    int acc = 0;
    while (peek() and isdigit(peek().value()))
      acc = (acc * 10) + read() - '0';
    return acc;
  }
};

class Solution {
 public:
  TreeNode* recoverFromPreorder(string S) {
    TreeNode* root = new TreeNode(-1);

    auto build = [&] {
      auto token   = tokenizer(S);
      auto parent  = unordered_map<TreeNode*, TreeNode*>{};
      auto builder = root;

      auto dfs = rec([&](auto&& dfs,
                         const optional<int>& id           = {},
                         const optional<string>& prev_move = {},
                         const optional<string>& cur_move  = {}) -> void {
        if (not id and not cur_move and not prev_move) {
          auto cur_id     = token.next<int>();
          builder->val    = cur_id;
          parent[builder] = builder;
          if (token.peek())
            dfs(optional<int>{token.next<int>()}, optional<string>{}, optional<string>{token.next<string>()});
        }
        else if (id and cur_move and (not prev_move or size(*prev_move) + 1 == size(*cur_move))) {
          builder->left         = new TreeNode(id.value());
          parent[builder->left] = builder;
          builder               = builder->left;
          if (token.peek())
            dfs(optional<int>{token.next<int>()}, cur_move, optional<string>{token.next<string>()});
        }
        else if (id and cur_move and prev_move and size(*prev_move) == size(*cur_move)) {
          builder                = parent[builder];
          builder->right         = new TreeNode(id.value());
          parent[builder->right] = builder;
          builder                = builder->right;
          if (token.peek())
            dfs(optional<int>{token.next<int>()}, cur_move, optional<string>{token.next<string>()});
        }
        else if (id and cur_move and prev_move and size(*prev_move) > size(*cur_move)) {
          builder = parent[builder];
          dfs(optional<int>{id}, optional<string>{(*prev_move).substr(1)}, cur_move);
        }
      });
      dfs();
    };
    return (build(), root);
  }
};