What is the difference between "Redeploy" and "Restart Server" in IntelliJ?

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.

Update resources. All changed resources (that is, all application components other than the classes) will be updated.

Update classes and resources. All changed resources will be updated; changed classes will be recompiled. In the debug mode, the updated classes will be hot-swapped. In the run mode, IntelliJ IDEA will just update the changed classes in the output folder. Whether such classes will actually be reloaded in the running application, depends on the capabilities of the runtime being used.

Redeploy. The application will be updated and redeployed.

Restart server. The server will be restarted. The updated version of the application will be deployed at the server startup. For packed artifacts, the available options are:

Hot swap classes. Changed classes will be recompiled and reloaded at runtime. Note that this option will work only in the debug mode. Redeploy. The overall application will be rebuilt and redeployed. Restart server. The server will be restarted. The application will be rebuilt and deployed at the server startup.

From: http://www.jetbrains.com/idea/webhelp/run-debug-configuration-tomcat.html