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
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
@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!
Thank you for a nice solution.
I am always surprised how you write the most concise solution.
Reading your solution is becoming an art form for me :D
@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.
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 to
max is a generator, which provides the values one by one on demand. And then
max 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/simple-python-bfs-beats-99-83-65ms
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 call
curr_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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.