Question: To all the people with good ears:

when you're figuring out a melody by ear, are you listening to the sequence of notes and figuring out where each note sits relative to the root of the key?  

Or are you figuring out what the next note is by the interval from the last note?

Answer: 
You have to learn motifs and intervals. (Make your self a list of the most usual like:
so-mi, so-la-so-mi, do-re-mi-do, do-re-mi-fa-so, so-do, so-do-mi, so-la-ti-do, do-do-ti-do, do-ti-la-ti-do etc. etc. and then you'll recognize them in a melody. There are lots of identical turns and formulas in folk or pop songs.

You can make (also when listening by ear) a harmonic analysis like a piano chord reduction, filtering out the triad (arpeggios) and add the other tones as change notes, passing tones and approach notes.

And you won't ask which method we prefer. Everyone uses both and not only these two. You can listen to the base line, the melody, the cadences and sequences and the transposed motifs. All are playing a role, all of them are helpful.

So start training scales, intervals, triads and 7th chords with their resolution like: so-ti-re-fa ->mi-do, by singing, writing, playing, listening.

do-re-do-mi-do-fa ... or do-mi-re-fa-mi-so (all combinations of intervals and sequences. That's what solfege is. Search for solfeggios and warming ups, also for piano etudes for beginners.
When playing by ear (or writing things down), I have a lot of mental scaffoldings in my head. Like a set of automatons working in parallel, each making sense of something else:

* relative intervals to the last sound
* relative interval to some sound I remember / can relate (e.g. when I play a 6 note motive I hear that the last note is fifth below the first one)
* possibilities of the current scale
* interval relative to bass
* typical harmonic behavior, like resolving dominant 3 or dominant seven (the longer one plays, the more behaviors they consider "typical")

Some of those automatons are more cerebral, and some work on the finger level (even when I am not playing an instrument and just jolting down notes, I actually move my fingers).

When I play "by ear", I see a set of "green lights" in my head: the automatons all confirm each other's choices. It's like: "OK, the next sound is a minor second below... check; it's minor seventh of a minor chord resolving to major third of a dominant... check; it is the seventh tone of the current scale... check; base jumps a perfect fourth up... check; it's the same sound we heard on the beginning of the phrase... check". Sometimes it happens that one of the machines says: "bzzzt! something's wrong!", and then a frantic voting happens, I have to take things off the auto pilot and fall back to 1 (just relative intervals).