Title: Binary Tree Zigzag Level Order Traversal Source: leetcode.com
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,#,#,15,7},
|
1 2 3 4 5 |
3 / \ 9 20 / \ 15 7 |
return its zigzag level order traversal as:
|
1 2 3 4 5 |
[ [3], [20,9], [15,7] ] |
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
''' https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ ''' # 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 __init__(self): self.res = [] self.length = 0 def helper(self, root, lvl): if self.length == lvl: self.res.append([root.val]) self.length += 1 else: if (lvl & 1) == 1: self.res[lvl].insert(0,root.val) else: self.res[lvl].append(root.val) if root.left: self.helper(root.left, lvl + 1) if root.right: self.helper(root.right, lvl + 1) def zigzagLevelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return self.res self.helper(root, 0) return self.res |