/103. Binary Tree Zigzag Level Order Traversal
Previous|Next

103. Binary Tree Zigzag Level Order Traversal

Medium
Trees63.3% acceptance

Given the root node of a binary tree, return a list of lists containing the values of the nodes in zigzag level order traversal. Zigzag traversal means that for each level, the order alternates between left-to-right and right-to-left.

Example 1

Input: TreeNode(5, TreeNode(2), TreeNode(8, TreeNode(6), TreeNode(10)))

Output: [[5],[8,2],[6,10]]

Explanation: Level 1: [5], Level 2: [8,2] (right-to-left), Level 3: [6,10] (left-to-right)

Example 2

Input: TreeNode(4, TreeNode(3, TreeNode(1)), TreeNode(7))

Output: [[4],[7,3],[1]]

Explanation: Level 1: [4], Level 2: [7,3] (right-to-left), Level 3: [1] (left-to-right)

Example 3

Input: TreeNode(11)

Output: [[11]]

Explanation: Single node tree

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= node value <= 100
Python (current runtime)

Case 1

Input: TreeNode(12, TreeNode(5, None, TreeNode(9)), TreeNode(18, TreeNode(14), None))

Expected: [[12],[18,5],[9,14]]

Case 2

Input: TreeNode(7, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(9, None, TreeNode(10)))

Expected: [[7],[9,3],[1,4,10]]

Case 3

Input: None

Expected: []