Beyond awesome | 越而胜己

This is obviously a BFS problem. Like LC45. Jump Game II, BFS itself is quite easy, but the key is to find the boundaries between two BFS layers in the traversal. Because the BFS in this problem is on an actual graph (tree), we need to maintain a queue q for BFS.

Before we begin BFS, q has one element root, according to the BFS algorithm; and level 0 happens to contain just root. After visiting root, q now has two elements: root.left and root.right, and these are the elements in level 1.

So, to figure out the boundary between levels, after traversing the previous level, count how many nodes are in this level (should be len(q)). Then we do the BFS loop len(q) times to finish iterating this level.

This method should also apply to generic graphs, with only slight modification of maintaining a discovered set to keep track of visited vertices.