def findValueMostElement(self, root):
maxes = []
row = [root]
while any(row):
maxes.append(max(node.val for node in row))
row = [kid for node in row for kid in (node.left, node.right) if kid]
return maxes
Python BFS

@StefanPochmann
Any
to deal will the case [None] is brilliant.
Could give some explanation on the code:[kid for node in row for kid in (node.left, node.right) if kid]
I have never used two
for
embedded.

@lee215 I'll try to explain this part. Please tell me if I'm wrong.
row = [kid for node in row for kid in (node.left, node.right) if kid]
is equal to:
row = [a,b,c,d...] xxx = [] for node in row: for kid in (node.left, node.right): if kid: xxx += kid, row = xxx
Note that @StefanPochmann keep updates the row list again and again. How great this is!

@StefanPochmann Just curious, is the max in "max(node.val for node in row)" taking the max at each sequential step or is it taking the max after the for loop is completed? Given that you don't need that extra for loop for calculating the max since you already go through each node in the row in the other for loop.

@livelearn said in Python BFS:
taking the max after the for loop is completed
Not sure what you mean with that...

@StefanPochmann For example, is it doing this:
maxx=inf("inf") for i in a: maxx=max(i,maxx) or for i in a tmp.append(i) max(tmp)

@livelearn It's neither of those. It looks more like your second version, as I call
max
just once and I do give it only one thing. But it really is more like your first version. That one thing I give tomax
is a generator, which provides the values one by one on demand. And thenmax
will, under the hood, do something like your first version.

@StefanPochmann Such condensed code, brilliant. The max per row and the row can be computed in the same pass to make the solution even quicker. I used the same BFS idea but computed max per row and rows in same pass.
Here's my solution: https://discuss.leetcode.com/topic/92079/simplepythonbfsbeats998365ms

@pramttl said in Python BFS:
to make the solution even quicker
Doesn't look quicker to me. Where are your statistics?
I did some myself now, renaming our function and adding this one:
def largestValues(self, root): for _ in range(100): answer = self._largestValues(root) return answer
Then I alternately submitted our solutions three times. The times (in ms):
mine yours 705 736 696 779 815 802
They look very similar, with mine looking a bit quicker. I doubt you tested this properly or at all.

@StefanPochmann In your solution there are 2 passes over the row, one to compute maximum and one to compute kids. Logically, wouldn't it be quicker to use a single pass to compute max and child row ?
I got 65 ms on Leetcode on submitting my solution (shared snapshot in comments section of my solution) and that's why I claimed it is quicker. Being new to Leetcode, wasn't aware that the runtime can vary so much on multiple submissions. (probably because of smaller test cases). I just wanted to highlight that single pass to compute row max and next row could be quicker if the tree is very large with several elements per row. If I am wrong, let me know ?

@pramttl Your single pass does more than each of my two passes. It does the same as both of mine together. Granted, the pure iteration is done twice in mine, but yours spends more time on each item. You're calling
max
for each node (I only call it once per row) and you look up and callcurr_level_nodes.append
for each node. List comprehensions do that more efficiently. Compare what happens in each iteration in loop+append vs list comprehension:>>> def f(): ans = [] for x in X: ans.append(x) return ans >>> import dis >>> dis.dis(f) 3 0 BUILD_LIST 0 3 STORE_FAST 0 (ans) 4 6 SETUP_LOOP 27 (to 36) 9 LOAD_GLOBAL 0 (X) 12 GET_ITER >> 13 FOR_ITER 19 (to 35) 16 STORE_FAST 1 (x) 5 19 LOAD_FAST 0 (ans) 22 LOAD_ATTR 1 (append) 25 LOAD_FAST 1 (x) 28 CALL_FUNCTION 1 31 POP_TOP 32 JUMP_ABSOLUTE 13 >> 35 POP_BLOCK 6 >> 36 LOAD_FAST 0 (ans) 39 RETURN_VALUE >>> def g(): return [x for x in X] >>> dis.dis(g) 3 0 BUILD_LIST 0 3 LOAD_GLOBAL 0 (X) 6 GET_ITER >> 7 FOR_ITER 12 (to 22) 10 STORE_FAST 0 (x) 13 LOAD_FAST 0 (x) 16 LIST_APPEND 2 19 JUMP_ABSOLUTE 7 >> 22 RETURN_VALUE
What the list comprehension does with a simple LIST_APPEND, the loop+append does with LOAD_FAST(ans), LOAD_ATTR(append), CALL_FUNCTION and POP_TOP.
I btw just tested a bit more and got very unstable times, from about 700 ms to about 1400 ms. I guess the server is under more load right now. Maybe because the Americans are awake now. Ideally one would extract all test cases and do local testing without other things on the PC going on, and repeat the tests even more often than just 100 times and do it more often than just three times. Though then you'd compare it on your PC and that might not be perfectly representative for running it on LeetCode (though that doesn't need to be bad). Anyway, it's a bit too much work for me to bother doing that now :P