Leetcode: Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal



Similar Problems:


Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/binary-tree-zigzag-level-order-traversal
## Basic Ideas: BFS, use left_to_right(boolen) for level traversal direction
## Complexity: Time O(n), Space O(k)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res = []
        queue = []
        queue.append(root)
        left_to_right = True
        while len(queue) != 0:
            length = len(queue)
            level_element = []
            for i in xrange(length):
                element = queue[0]
                del queue[0]
                if left_to_right is True:
                    level_element.append(element.val)
                else:
                    level_element.insert(0, element.val)
                if element.left:
                    queue.append(element.left)
                if element.right:
                    queue.append(element.right)
            res.append(level_element)
            left_to_right = not left_to_right
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.