I have a deer crossing sign in my yard and get to garden with a thriving community of urbanized deer (they are so tame that I can hit them throwing a golf ball). They get curious about anything new they see. From my observation, I doubt many deer try the leaves more than once (except in situations where food is scarce). That said, I nearly lost my in ground first year LSU purple after several deer decided to have a tastes. They won't finish off an entire plant overnight like they will for hydrangea, plum, tomato, mulberry or blueberry. I would think any tree with more than 20+ leaves is safe to leave around them.
A rutting buck is another story. Be careful in late fall as they will tear any small tree to shreds.