_103. Binary Tree Zigzag Level Order Traversal.md

103. Binary Tree Zigzag Level Order Traversal

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 03, 2024

Last updated : July 03, 2024

---

Related Topics : Tree, Breadth-First Search, Binary Tree

Acceptance Rate : 60.2 %

---

Solutions

• 103.binary-tree-zigzag-level-order-traversal.py
• m103.py

Python

103.binary-tree-zigzag-level-order-traversal.py

# 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]]:
        

m103.py

# 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]]:
        if not root :
            return []
        toVisit = deque([root])
        leftRight = True
        output = []

        while toVisit :
            width = len(toVisit)
            lvl = []
            for i in range(width):
                if leftRight :
                    curr = toVisit.popleft()
                    lvl.append(curr.val)
                    if curr.left :
                        toVisit.append(curr.left)
                    if curr.right :
                        toVisit.append(curr.right)
                else :
                    curr = toVisit.pop()
                    lvl.append(curr.val)
                    if curr.right :
                        toVisit.appendleft(curr.right)
                    if curr.left :
                        toVisit.appendleft(curr.left)

            output.append(lvl)
            leftRight = not leftRight
        return output