def verticalOrder(self, root): cols = collections.defaultdict(list) queue = [(root, 0)] for node, i in queue: if node: cols[i].append(node.val) queue += (node.left, i - 1), (node.right, i + 1) return [cols[i] for i in sorted(cols)]
changing a list while iterating over it feels like anti-pattern to me. (I know you are just appending items to it, not removing items from it, but I still think use an extra counter variable with len(queue) is a bit better.
@bryan.chou.121 Yeah, I know... I just prefer focusing on the actual algorithm, so I like doing it this short way. I'm sure I've mentioned before that to my knowledge this isn't guaranteed to work, but while I'm always aware of it, I really don't feel like explaining it every time. Maybe I should just stop using it...
Ok I just wrote the two obvious clean replacements. Meh... I wish they'd just define my iteration to work.
def verticalOrder(self, root): cols = collections.defaultdict(list) queue = collections.deque([(root, 0)]) while queue: node, i = queue.popleft() if node: cols[i].append(node.val) queue += (node.left, i - 1), (node.right, i + 1) return [cols[i] for i in sorted(cols)] def verticalOrder(self, root): cols = collections.defaultdict(list) queue = [(root, 0)] i = 0 while i < len(queue): node, x = queue[i] i += 1 if node: cols[x].append(node.val) queue += (node.left, x - 1), (node.right, x + 1) return [cols[x] for x in sorted(cols)]
Most highly voted answers for this question are incorrect.
Given a perfect 4-level binary tree, named by level: 1; 2,3; 4,5,6,7; 8,9,10,11,12,13,14,15, I got this result: [, , [2, 9, 10, 12], [1, 5, 6], [3, 11, 13, 14], , ]. See that 12 runs into a bucket ahead of 11's. I don't think that's right. The correct answer should be [,,[2,9,10],,[1,11,12],,[3,13,14],,]. Draw the tree on a paper, you'll see.
My ugly drawing is here:
Stefan, pls validate my comment below, with a drawing. It seems a good solution for this problem should go bottom-up, and/or considering the levels/depth then expanding to the buckets.
No, you're just misunderstanding the problem.
You yourself put 2 and 9 in the same column, which is correct because from 2 you go one left and one right. But then you should also put 1 and 5 into the same column, for the exact same reason.
But, I still feel that interleaving node branches into columns is a bit strange. I wonder if there's a clear definition for a "column" for this problem.
yeah, i got the same confusion. the question actually assumes the nodes have the same width to its neighbors (which is missing in the statement), so they could cross over each other. However, if you enumerate the nodes straightly without any overlap, as drawn in the nick46's "ugly" image, the "vertical" result is totally dependent on the shape of the tree. The latter problem is far more difficult to solve.
But as @nick46 point out, how to explain
12 runs into a bucket ahead of 11's? This is weird.....
As @StefanPochmann said,
2 -> 9 is through one left, one right, and the same width means with the same
steps goes from a node. If this is kind of the definition of width, I got more confused now....
@StefanPochmann Could've done something like this:
class Solution(object): def verticalOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return  d=collections.defaultdict(list) q=[(root,0)] for node,i in q: if node: d[i].append(node.val) q.append((node.left,i-1)) q.append((node.right,i+1)) ret=*len(d) diff=-min(d.keys()) for k,v in d.items(): ret[k+diff]=v return ret
@livelearn That's more complicated, though. And probably slower.
@StefanPochmann Don't see how it's slower considering you're using a sort function. The time complexity of mine is O(n), I doubt it's slower, unless python's timesort came into play here.
@livelearn Well, here are some test results. I created the dictionary with keys from -n to n in random order and then ran mine against yours. The floats are times in seconds.
n: 1 stefan: 7.680 livelearn: 9.603 n: 10 stefan: 2.601 livelearn: 2.678 n: 100 stefan: 1.697 livelearn: 1.878 n: 1000 stefan: 1.273 livelearn: 1.932 n: 10000 stefan: 1.200 livelearn: 2.169 n: 100000 stefan: 2.198 livelearn: 4.137 n: 1000000 stefan: 3.301 livelearn: 5.604
The testing script:
from collections import defaultdict from random import shuffle from timeit import timeit def stefan(cols): return [cols[i] for i in sorted(cols)] def livelearn(d): ret=*len(d) diff=-min(d.keys()) for k,v in d.items(): ret[k+diff]=v return ret for e in range(7): n = 10**e r = range(-n, n) shuffle(r) cols = defaultdict(list) for i in r: cols[i].append(i) ts = timeit(lambda: stefan(cols), number=10**7 / n) tl = timeit(lambda: livelearn(cols), number=10**7 / n) print 'n: %7d stefan: %6.3f livelearn: %6.3f' % (n, ts, tl)
I think most of that time is coming from from the line diff=-min(d.keys()), I could simply calculate the min in the original for loop. That could make mine faster than yours if that line is taken out.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.