You can find a Leaf Stone at Route 119, at the bottom of the river.
You can also get a Leaf Stone by trading a Green Shard with the diving treasure hunter, found in a little house on a little island to the east of Route 124.
To obtain the Green Shards, get HM Dive and go underwater and explore the seaweeds until you come across a Relicanth. (If you catch a Relicanth, there's a chance that it will be holding a Leaf Stone.)
There is also a Green Shard on Route 124, which you can obtain by finding a diving spot shaped like a cross and dive. Once your underwater, go to your left and there will be a square out line, dive up then go downwards. Keep swimming to your left until you see a diving spot that's shaped like a square. Just like when you're on the sea floor, dive under then keep going until you see another diving spot, once you find it, go up and there will be a Green Shard on the land.
Hope I helped :)