#include "s0257_binary_tree_paths.hpp"

struct TreeNodeState_S0257 {
  TreeNode* ptr;
  string path;
};

vector<string> S0257::binaryTreePaths(TreeNode* root) {
  queue<TreeNodeState_S0257> q;
  vector<string> result{};
  if (root) q.push(TreeNodeState_S0257{root, std::to_string(root->val)});
  while (!q.empty()) {
    TreeNodeState_S0257 front = q.front();
    q.pop();
    if (front.ptr->left == nullptr && front.ptr->right == nullptr)
      result.push_back(front.path);
    if (front.ptr->left)
      q.push(TreeNodeState_S0257{
          front.ptr->left,
          front.path + "->" + std::to_string(front.ptr->left->val)});
    if (front.ptr->right)
      q.push(TreeNodeState_S0257{
          front.ptr->right,
          front.path + "->" + std::to_string(front.ptr->right->val)});
  }
  return result;
}