ZigZag Order traversal

1. Link

2. 描述

[[3],[20,9],[15,7]]

示例1

输入：

{1,#,2}

复制返回值：

[[1],[2]]

3. 思路

BFS using queue to traverse the tree as usual
but when appending node to queue, we append them to the second queue, the queue storing the nodes in the next level
we also append the values of current nodes to a list
when queue is empty and nodes in current level are finished, check if we need to reverse result in the current list and reverse them if necessary, then update queue with the nodes in the second queue in the next level.

4. Coding

class Solution:
    def zigzagLevelOrder(self , root ):
        # input: tree root 
        # output: traversal results
        # idea: BFS
        # 1.  traverse the tree in level-order as usual, but append the result
        #    of the same level to the second queue
        # 2. reverse the result queue if needed
        #
        # use a queue to store the node of current leve l
        # second queue to store nodes of the next level
        # loop until queue is empty
        #    pop the node from queue  
        #    add children to second queue
        #    when queue is empty, this level is finished
        #    append reverse node value in next level to res
        #    update queue
        
        if not root:
            return []
        queue = [root]
        level = []
        level_res = []
        res = []
        reverse = False
        while queue:
            node = queue.pop(0)
            if node.left:
                level.append(node.left)
            if node.right:
                level.append(node.right)
            # append result of current level
            level_res.append(node.val)
            if not queue:
                if reverse:
                    # reverse the next level
                    level_res.reverse()
                reverse = not reverse
                res.append(level_res[:])
                queue = level[:]
                level = []
                level_res = []
        return res

PreviousCheck BST and Check CompleteTree NextBinary Tree diameter I

Last updated 3 years ago

Was this helpful?

class Solution: def zigzagLevelOrder(self , root ): # input: tree root # output: traversal results # idea: BFS # 1. traverse the tree in level-order as usual, but append the result # of the same level to the second queue # 2. reverse the result queue if needed # # use a queue to store the node of current leve l # second queue to store nodes of the next level # loop until queue is empty # pop the node from queue # add children to second queue # when queue is empty, this level is finished # append reverse node value in next level to res # update queue if not root: return [] queue = [root] level = [] level_res = [] res = [] reverse = False while queue: node = queue.pop(0) if node.left: level.append(node.left) if node.right: level.append(node.right) # append result of current level level_res.append(node.val) if not queue: if reverse: # reverse the next level level_res.reverse() reverse = not reverse res.append(level_res[:]) queue = level[:] level = [] level_res = [] return res