class Solution {
 public:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ans;
    dfs(root, {}, ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, vector<string>&& path, vector<string>& ans) {
    if (!root)
      return;
    if (!root->left && !root->right) {
      ans.push_back(join(path) + to_string(root->val));
      return;
    }

    path.push_back(to_string(root->val) + "->");
    dfs(root->left, move(path), ans);
    dfs(root->right, move(path), ans);
    path.pop_back();
  }

  string join(const vector<string>& path) {
    string joined;
    for (const string& s : path)
      joined += s;
    return joined;
  }
};

class Solution {
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> ans = new ArrayList<>();
    dfs(root, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(TreeNode root, StringBuilder sb, List<String> ans) {
    if (root == null)
      return;
    if (root.left == null && root.right == null) {
      ans.add(sb.append(root.val).toString());
      return;
    }

    final int length = sb.length();
    dfs(root.left, sb.append(root.val).append("->"), ans);
    sb.setLength(length);
    dfs(root.right, sb.append(root.val).append("->"), ans);
    sb.setLength(length);
  }
}

class Solution:
  def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    ans = []

    def dfs(root: Optional[TreeNode], path: List[str]) -> None:
      if not root:
        return
      if not root.left and not root.right:
        ans.append(''.join(path) + str(root.val))
        return

      path.append(str(root.val) + '->')
      dfs(root.left, path)
      dfs(root.right, path)
      path.pop()

    dfs(root, [])
    return ans