Optimizing Fleury's algorithm to work in O(|V|+|E|)
Because a bridge in current graph may not be a bridge in the primary graph. Note Fleury's Algorithm deletes an edge after you pass it.

Consider the following graph:



You start at $A$, then move to $B$ and delete the edge $AB$. 



Now $BE$ becomes a bridge so the algorithm then chooses $BC$. However, $BE$ is not a bridge in the primary graph, so you cannot detect it in advance.

According to Wikipedia


  If there are no vertices of odd degree, all Eulerian trails are
  circuits. If there are exactly two vertices of odd degree, all
  Eulerian trails start at one of them and end at the other.


So finding an Eulerian trail is essentially the same as finding a cycle (if there are exactly two vertices of odd degree, add an edge connecting them and find an Eulerian cycle in the new graph).