Note that the url-rewriting doesn’t directly determine the template used. A pretty url is interpreted as a query and then that query determines what template is used based on the template hierarchy.
So only need one rule:
example.com/localdeals/myterm => example.com/?location=myterm
WordPress will look for the template taxonomy-location-myterm.php
and use that (if it exists) or otherwise fallback to taxonomy-location.php
To add the above rule, when you register your taxonomy:
register_taxonomy('location','post',array(
'hierarchical' => false,
...
'query_var' => true,
'rewrite' => array( 'slug' => 'localdeals' ),
...
));
(you will need to flush these rules once after changing these – if this is for a plug-in/theme, only flush on activation/de-activation). Otherwise, just visit Settings > Permlinks page, and they’ll be flushed :).