Idea This problem is natural to use BFS search. and record the first node at each level, then return the last node value.