Take the elevator behind the throne platform down, and use the teleporter shrine by the left wall in the dining room. If that elevator is blocked off by a forcefield, take the main door out of the throne room, to get to the trainer's platform, and go grab the dragon stone (after you take out enough opponents, you will automatically return to the battle tower and be able to teleport out).
Once you get to the teleporter shrine outside on Sentinel Island (the one by the locked door into the battle tower is above the poison gas), jump up the nearby rocks and run over to an area where there are no over-hanging branches in order to turn into a dragon and fly to the ship in the tree (there are a few other things around to find / loot, as well, in addition to the remaining opponents you can finish off).
