Restart server does exactly what it says, and restarts the tomcat server. Your war will be rebuilt and deployed at server startup. This is useful if you are having trouble hot-swapping your classes.
Redeploy will redeploy the entire .war (without restarting the server), as opposed to trying to hot-swap out changed classes and other resources.
See also: http://www.jetbrains.com/idea/webhelp/updating-a-running-java-ee-application.html
In answer to your second question, a redeploy should be sufficient. That said, it can cause memory leaks and is often only slightly faster than a full restart.