Python BFS solution with clear comments


  • 0
    class Solution(object):
        def zigzagLevelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            res = [] # result list
            cnt = 0 # use to toggle printed order
            if not root:
                return res
            now = [root]
            while now:
                cnt += 1
                tmp = [] # next level elements
                vals = [] # current level's node value
                for x in now:
                    vals.append(x.val)
                    if x.left:
                        tmp.append(x.left)
                    if x.right:
                        tmp.append(x.right)
                # zigzag
                if cnt % 2 == 1:
                    res.append([v for v in vals])
                else:
                    res.append([v for v in reversed(vals)])
                # progress level
                now = tmp
            return res
    

    The idea is simple. I use a counter to determine whether to print the current level in normal order or reversed order. And be sure to put node.val instead of node to the final result.


Log in to reply
 

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