def firstUniqChar(self, s: str) -> int:
        # 1. set up a hashmap and put each letter and its count from s into it
        hashmap = {}
        for letter in s:
            hashmap[letter] = hashmap.get(letter, 0) + 1
        # 2. now go thru the indices in s, and check if the corresponding letter for that index is in the hashmap, if it is and the count is 1, return the index
        for i in range(len(s)):
            # 2.1 remember that dicts in python 3.7 and later are ordered
            if hashmap[s[i]] == 1:
                return i
        # 3. else return -1
        return -1

# 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
from collections import deque
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # if root is None return an empty array, otherwise make an empty answer array
        if root is None:
            return []
        answer = []
        
        
        def dfs(node, level):
            # appends to the answer once the level is >= to the length of the answer array
            if level >= len(answer):
                answer.append(deque([node.val]))
            else:
                if level % 2 == 0:  # if even
                    answer[level].append(node.val)
                else:  # if odd
                    answer[level].appendleft(node.val)
            
            # continues the function as long as there are next nodes in the next level
            for next_node in [node.left, node.right]:
                if next_node is not None:
                    dfs(next_node, level + 1)
        
        # start the dfs function with the root node and a level of 0
        dfs(root, 0)
        
        # return the answer array at the end
        return answer