It is technically not legal; but how to handle this situation will depend largely on your playgroup’s style and friendliness.
Playing the Deserter card when you don’t have a space to place your new Knight is completely legal:
Progress Cards: Deserter - May I play the Deserter if I can’t place a knight of the same strength?
Also, the act of placing your own knight is optional; the card says you “may” place a knight.
So technically, as soon as the player revealed the card and chose the opponent, the card should be considered played, and now that the card has been played, it would be too late to construct a road before the card is finished getting played.
During your turn, after you have rolled the dice, you may play any number of progress cards in any order. You may play them between other actions taken during your turn. When you play a progress card, resolve all of its effects, then place it, face down, under the progress card stack of the matching color.
However, with pretty much any playgroup I know, the players would allow this, assuming that the player did not get any extra knowledge by playing the card that caused them to decide to build a road. There are 2 possibilities here:
If the player needed to build a road in order place his own knight no matter what, then I and anyone I’d be likely to play with would allow the player to build the road first; basically temporarily undoing the move. Little mistakes like that happen often in board games, and we generally allow the player to fix it if he catches it immediately and before anything else has changed.
If the opponent's choice of which knight to remove affected the decision to build a road, then we would not allow it to be undone. For example, if the opponent had 2 knights; one was in a space where the active player could place a knight, and the second was not. The attacked player chose the second knight, which left the active player with no space place a knight. But had the attacked player chosen the first knight, then a new road would not be necessary. In this case, playing the card without building a road first would not be an obvious mistake; but could be seen as a gamble that the opponent would chose the first knight.