/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. For each level, alternate the traversal direction: left-to-right for one level, then right-to-left for the next, and so on.

Example 1

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

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

Explanation: Level 1: [5] left-to-right; Level 2: [8,2] right-to-left; Level 3: [7,10] left-to-right.

Example 2

Input: TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))

Output: [[1],[3,2],[4,5]]

Explanation: Level 1: [1]; Level 2: [3,2]; Level 3: [4,5].

Example 3

Input: None

Output: []

Explanation: Empty tree returns empty list.

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= node value <= 100.
  • Input is a binary tree; each node has at most two children.
  • Return an empty list if the tree is empty.
Python (current runtime)

Case 1

Input: TreeNode(10, TreeNode(6, TreeNode(4), TreeNode(7)), TreeNode(15, None, TreeNode(20)))

Expected: [[10],[15,6],[4,7,20]]

Case 2

Input: TreeNode(3, TreeNode(1), None)

Expected: [[3],[1]]

Case 3

Input: TreeNode(9, None, TreeNode(12, TreeNode(11), None))

Expected: [[9],[12],[11]]