@schumpeter I agree that the space cost of DFS would be better than BFS. But I think the size of the queue maintained in BFS would not be as big as 2^lgN, which is N, rather, I think it would be N/2. Because you only maintain actually one level in the queue. And the size of the largest level is N/2.
LeetCode Weekly Contest 19