Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
3 / \ 9 20 / \ 15 7Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]Example 2:
Input: root = [1]
Output: [[1]]Example 3:
Input: root = []
Output: []Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
Binary Tree Zigzag Level Order Traversal (via Breadth First Search Algorithm)
The standard Breadth First Search (BFS) traverses level by level order, and each level from left to right. Here is the standard BFS in Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] if not root: return ans q = deque([root]) while q: n = len(q) cur = [] for _ in range(n): x = q.popleft() cur.append(x.val) for kid in (x.left, x.right): if kid: q.append(kid) ans.append(cur) return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if not root:
return ans
q = deque([root])
while q:
n = len(q)
cur = []
for _ in range(n):
x = q.popleft()
cur.append(x.val)
for kid in (x.left, x.right):
if kid:
q.append(kid)
ans.append(cur)
return ansThe time/space complexity is O(N) where N is the number of the nodes given in the binary tree. And for the Zig-Zag, we just need to reverse the rows of the even numbers. Thus, with a slight modification, here is the Zig-zag traversal that reverses the even rows e.g. from right to left.
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 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] if not root: return ans q = deque([root]) while q: n = len(q) cur = [] for _ in range(n): x = q.popleft() cur.append(x.val) for kid in (x.left, x.right): if kid: q.append(kid) if len(ans) & 1: # <----- if the next row is even number, we reverse it ans.append(cur[::-1]) else: ans.append(cur) return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if not root:
return ans
q = deque([root])
while q:
n = len(q)
cur = []
for _ in range(n):
x = q.popleft()
cur.append(x.val)
for kid in (x.left, x.right):
if kid:
q.append(kid)
if len(ans) & 1: # <----- if the next row is even number, we reverse it
ans.append(cur[::-1])
else:
ans.append(cur)
return ansThe extra time complexity here (ZigZag Traversal Order) is to reverse, which at most N//2 nodes. So thus, the time/space complexity is still O(N).
Of course, we can use Depth First Search Algorithm (both Recursive or Iterative) to perform a Zig-zag traversal order.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Minimum Distance Between Binary Search Tree (BST) Nodes (Recursive Depth First Search + In-Order Traversal Algorithm)
Next Post: How ChatGPT Solves a Math Puzzle?