Replacing timber and tiles isn't difficult, certainly not in comparison with sourcing, cutting and placing stone.
The stone Notre Dame is built from actually comes from underground Paris
The city is riddled with catacombes which were originally the underground quarries the limestone came from.
Those same catacombes have periodically been used to empty the graveyards of Paris into, huge quantities of skeletons are down there, mostly not in the neatly ossuaries that the tourists can see but large dumps of skulls and bones.
Over the centuries much remedial work has had to be done as large areas of Paris were sinking in to the quarries below
You can navigate much of Paris below ground in the catacombes, I did spend a weekend down there a few years ago and the network is vast.