Python solution


  • 48
    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)]

  • 0
    C

    Brilliant solution!!


  • 2
    B

    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.


  • 0

    @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...


  • 10

    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)]
    

  • 1
    B

    Sorry haha I might adhere to certain conventions too much. Great solution!


  • 0
    N

    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: [[8], [4], [2, 9, 10, 12], [1, 5, 6], [3, 11, 13, 14], [7], [15]]. See that 12 runs into a bucket ahead of 11's. I don't think that's right. The correct answer should be [[8],[4],[2,9,10],[5],[1,11,12],[6],[3,13,14],[7],[15]]. Draw the tree on a paper, you'll see.

    My ugly drawing is here:
    http://postimg.org/image/w6yrf356n


  • 0
    N

    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.


  • 0

    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.


  • 0
    N

    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.


  • 0
    P

    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.


  • 0

    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....


  • 0
    L

    Didn't really need to sort


  • 0

    @livelearn said in Python solution:

    Didn't really need to sort

    But what's your alternative?


  • 0
    L

    @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=[0]*len(d) 
            diff=-min(d.keys())
            for k,v in d.items():
                ret[k+diff]=v
            return ret

  • 0

    @livelearn That's more complicated, though. And probably slower.


  • 0
    L

    @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.


  • 1

    @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=[0]*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)
    

  • 0
    L

    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.


  • 0

    @livelearn said in Python solution:

    I could simply calculate the min in the original for loop. That could make mine faster than yours if that line is taken out.

    I'm pretty sure that would make your solution slower, not faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.