重生之我还在做 HOT100

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = defaultdict(lambda : -1) # 哈希表缺省值
        n = len(nums)
        for i in range(n):
            if m[target - nums[i]] != -1:
                return [i, m[target - nums[i]]]
            m[nums[i]] = i
        return []

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        n = len(strs)
        m = defaultdict(list)
        for i in range(n):
            tmp_s = ''.join(sorted(strs[i])) # 注意下 str 的 join 用法
            m[tmp_s].append(strs[i])
        ans = []
        for i, v in m.items():
            ans.append(v)
        return ans

# 桶 + 技巧
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        m = set(nums)
        ans = 0
        for x in m: # !注意此处是在 set 中遍历，在 nums 中遍历最差是 On2
            if x - 1 in m:
                continue
            xx = x
            length = 0
            while xx in m:
                length += 1
                xx += 1
            ans = max(ans, length)
        return ans

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        stack_size = 0
        for i in range(n):
            if nums[i] != 0:
                nums[i], nums[stack_size] = nums[stack_size], nums[i]
                stack_size += 1

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        ans = 0
        while l < r:
            ans = max(ans, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = set()
        for i, x in enumerate(nums):
            l = i + 1
            r = n - 1
            while l < r:
                if nums[l] + nums[r] == -x:
                    ans.add((nums[i], nums[l], nums[r]))
                    # break 
                    # 注意下此处不能直接 break，因为同一个 i，可以对应不同的 l r 做答案
                    l += 1 
                    r -= 1
                elif nums[l] + nums[r] < -x:
                    l += 1
                else:
                    r -= 1
        res = []
        for x in ans:
            res.append([x[0], x[1], x[2]])
        return res

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = n - 1
            x = nums[i]
            while j < k:
                # print(i, j, k)
                if x + nums[j] + nums[k] == 0:
                    ans.append([x, nums[j], nums[k]])
                    j += 1
                    k -= 1
                    while 0 < j < k and nums[j] == nums[j - 1]:
                        j += 1
                    while j < k < n - 1 and nums[k] == nums[k + 1]:
                        k -= 1
                if x + nums[j] + nums[k] < 0:
                    j += 1
                if x + nums[j] + nums[k] > 0:
                    k -= 1
        return ans

# 前缀后缀
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        pre = [0] * n
        pre[0] = height[0]
        suf = [0] * n
        suf[-1] = height[-1]
        for i in range(1, n):
            pre[i] = max(pre[i - 1], height[i])
        
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], height[i])
        ans = 0
        for i in range(n):
            ans += (min(pre[i], suf[i]) - height[i])
        return ans

# 双指针，谁小谁移动
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        pre_max = height[l]
        suf_max = height[r]
        ans = 0
        while l < r:
            if pre_max < suf_max:
                ans += (pre_max - height[l])
                l += 1
            else:
                ans += (suf_max - height[r])
                r -= 1
            pre_max = max(pre_max, height[l]) 
            suf_max = max(suf_max, height[r])
        return ans

# 单调栈做法
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        n = len(height)
        ans = 0
        for i, x in enumerate(height):
            while stack and x >= height[stack[-1]]:
                bottom = height[stack[-1]]
                stack.pop()
                if not stack:
                    break
                l = stack[-1]
                h = min(height[l], x) - bottom
                ans += h * (i - l - 1)
            stack.append(i)
        return ans

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        m = defaultdict(int)
        l = r = ans = 0
        while l <= r and r < n:
            m[s[r]] += 1
            # print(m)
            while l <= r and m[s[r]] != 1:
                # print(l, r, m)
                m[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
            r += 1
        return ans

# 滑动窗口板子
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n = len(s)
        l = r = 0
        t = defaultdict(int)
        for i in list(p):
            t[i] += 1
        m = defaultdict(int)
        ans = []
        while l <= r and r < n:
            m[s[r]] += 1
            while l <= r and m[s[r]] > t[s[r]]: # 注意下缩左窗口的条件
                m[s[l]] -= 1
                l += 1
            # print(r, l, m)
            if r - l + 1 == len(p):
                ans.append(l)
            r += 1
        return ans

# 求区间和 -> 前缀和 -> 哈希记录出现的指定前缀数量
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        m = defaultdict(int)
        m[0] = 1
        ans = 0
        # prefix[x] - prefix[y] == k
        # 即找 m[prefix[i] - k] 的数量
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]
            ans += m[prefix[i] - k]
            m[prefix[i]] += 1
        return ans
         

# 单调队列
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        arr = deque()
        n = len(nums)
        r = 0
        ans = []
        while r < n:
            # print(r, arr)
            if r >= k:
                ans.append(nums[arr[0]])
                if arr[0] == r - k: # 维护左下标
                    arr.popleft() 
            
            while arr and nums[r] >= nums[arr[-1]]: # 入队列操作和单调栈一样
                arr.pop()
            arr.append(r)
            r += 1
        ans.append(nums[arr[0]])
        return ans

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)
        l = r = 0
        target = defaultdict(int)
        for i in list(t):
            target[i] += 1
        m = defaultdict(int)

        less = len(target) # 开始时 target 中每个词都没被满足
        ans_l, ans_r = 0, inf
        while l <= r and r < n:
            m[s[r]] += 1
            if m[s[r]] == target[s[r]]: # 注意此处一定是等于，只想让 less 更新一次
                less -= 1

            while l <= r and less == 0: 
                # print(l, r, less, ans_l, ans_r)
                if (ans_r - ans_l) > (r - l): # 注意此时内层循环才满足答案吗要求
                    ans_l = l
                    ans_r = r
                m[s[l]] -= 1
                if m[s[l]] == target[s[l]] - 1:
                    less += 1 # 同样的，保证 less 只更新一次
                l += 1
            r += 1
        return s[ans_l:ans_r + 1] if ans_r != inf else ""

# 找个前缀就可以
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = 0
        pre_min = inf
        ans = -inf
        for i in range(1, n + 1):
            pre_min = min(prefix, pre_min)
            prefix = prefix + nums[i - 1]
            ans = max(ans, prefix - pre_min)
        return ans

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        l = intervals[0][0]
        r = intervals[0][1]
        for x, y in intervals:
            if x <= r:
                r = max(y, r)
            else:
                ans.append([l, r])
                l = x
                r = y
        ans.append([l, r])
        return ans

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 自带的 reverse 会产生多余空间，自己用双指针搓更合适
        def reverse(l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        n = len(nums)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

# 前缀后缀积，最好用一个数组解决
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [1] * n
        for i in range(n - 1, 0, -1):
            suf[i - 1] = suf[i] * nums[i]
        # print(suf)
        
        pre = 1
        for i in range(n):
            suf[i] *= pre
            pre *= nums[i]
        return suf

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n): # 对齐下标
            nums[i] -= 1
        for i in range(n):
            while 0 <= nums[i] < n and nums[i] != nums[nums[i]]:
                j = nums[i] # 要让 swap 不被依赖
                nums[i], nums[j] = nums[j], nums[i]
        # print(nums)
        for i in range(n):
            if nums[i] != i:
                return i + 1
        return n + 1

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        m = len(matrix[0])
        col_0 = False
        raw_0 = False
        # 用 bool 记录第一行或列自己是否要归零
        for i in range(n):
            if matrix[i][0] == 0:
                raw_0 = True
                break
        for i in range(m):
            if matrix[0][i] == 0:
                col_0 = True
                break
        # 用第一行和第一列的来记录本行或列是否要归零
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0
        # 从第二行列开始进行实际归零
        for i in range(1, n):
            for j in range(1, m):
                if matrix[i][0] == 0:
                    matrix[i][j] = 0
                if matrix[0][j] == 0:
                    matrix[i][j] = 0
        # 修改第一行列
        for i in range(n):
            if raw_0:
                matrix[i][0] = 0
        for i in range(m):
            if col_0:
                matrix[0][i] = 0

# 走格子模拟，要注意些细节。注意要记录每行列的起始和方向。
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        index = 0
        ans = []
        m = len(matrix)
        n = len(matrix[0])
        px = py = 0
        left_m, right_m = 0, m
        left_n, right_n = 0, n
        while len(ans) != n * m:
            # print(ans, px, py, left_m, right_m, left_n, right_n)
            dx = direction[index][0]
            dy = direction[index][1]
            while left_m <= px < right_m and left_n <= py < right_n:
                # print(ans, px, py, left_m, right_m, left_n, right_n)
                ans.append(matrix[px][py])
                px += dx
                py += dy
            px -= dx # 循环后要把位置挪到下一个的起始点
            py -= dy
            ne = (index + 1) % 4
            px += direction[ne][0]
            py += direction[ne][1]
            if index == 0: # 维护边界
                left_m += 1
            if index == 1:
                right_n -= 1
            if index == 3:
                left_n += 1
            if index == 2:
                right_m -= 1
            index = (index + 1) % 4

        return ans

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # print(matrix)

        mid = n // 2
        for i in range(m):
            for j in range(mid):
                matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        x, y = 0, n - 1
        while x < m and y >= 0:
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                y -= 1
            elif matrix[x][y] < target:
                x += 1
        return False

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p = headA
        q = headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p 

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head
        nxt = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return nxt

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 快慢指针找中点
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        def reverse(head):
            cur = head
            pre = None
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre
        # 反转后半段
        right = reverse(slow)
        left = head
        # 判断前后是否相同
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        slow = fast = head
        fast = slow.next
        while slow != fast and slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return True if slow == fast else False

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        if not fast or not fast.next:
            return
        
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next

        return fast

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        prehead = ListNode(-1)
        pre = prehead # 用一个 pre 来链接链表
        cur1 = list1
        cur2 = list2
        while cur1 and cur2:
            if cur1.val <= cur2.val: # 谁小谁移动
                pre.next = cur1
                cur1 = cur1.next
                pre = pre.next
            else:
                pre.next = cur2
                cur2 = cur2.next
                pre = pre.next
        if cur1:
            pre.next = cur1
        else:
            pre.next = cur2
        return prehead.next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur1 = l1
        cur2 = l2
        # 将 cur1 的值加到 cur2 中，注意如果 cur1 更长或者有进位，需要加节点
        while cur1 and cur2: 
            if not cur2.next and cur1.next:
                cur2.next = ListNode(0)
            cur2.val += cur1.val
            if cur2.val >= 10:
                cur2.val %= 10
                if cur2.next:
                    cur2.next.val += 1 
                else:
                    node = ListNode(1)
                    cur2.next = node
            cur2 = cur2.next
            cur1 = cur1.next
        # 如果 cur2 最后还是大于 10，则反复加节点
        while cur2 and cur2.val >= 10:
            cur2.val %= 10
            if cur2.next:
                cur2.next.val += 1 
            else:
                node = ListNode(1)
                cur2.next = node
            cur2 = cur2.next
        return l2

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = head
        for _ in range(n):
            fast = fast.next
        slow = head
        prehead = ListNode(-1)
        pre = prehead
        pre.next = head
        while fast:
            fast = fast.next
            pre = slow
            slow = slow.next
        pre.next = slow.next
        del slow
        return prehead.next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prehead = ListNode(-1)
        pre = prehead
        pre.next = head
        cur = head
        while cur:
            nx = cur.next
            if not nx:
                return prehead.next
            pre.next = nx
            tmp = nx.next
            nx.next = cur
            cur.next = tmp
            
            pre = cur
            cur = cur.next
        return prehead.next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        guard = ListNode(-1)
        guard.next = head
        def reverse(head: Optional[ListNode], k: int):
            cur = head
            pre = None
            kk = k
            while cur and k:
                k -= 1
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            # print(pre, head)
            return pre, head

        cur = head
        pre = guard
        while cur:
            tail = cur
            for i in range(k - 1):
                tail = tail.next
                if not tail:
                    return guard.next
            tail = tail.next
            l, r = reverse(cur, k)
            pre.next = l
            r.next = tail
            # print(tail)
            pre = r
            cur = tail

        return guard.next

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        m = defaultdict(Node)
        cur = head
        pre = Node(-1)
        pre.next = cur
        while cur:
            new_node = Node(cur.val, None, None)
            m[cur] = new_node
            cur = cur.next
        cur = head
        print(m[head])
        while cur:
            if cur.next:
                m[cur].next = m[cur.next]
            if cur.random:
                m[cur].random = m[cur.random]
            cur = cur.next
        return m[head] if head else None

# 递归法更好写
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 合并链表
        def mergeList(head1, head2):
            prehead = ListNode(-1)
            pre = prehead
            cur1 = head1
            cur2 = head2
            while cur1 and cur2:
                if cur1.val <= cur2.val:
                    pre.next = cur1
                    cur1 = cur1.next
                else:
                    pre.next = cur2
                    cur2 = cur2.next
                pre = pre.next
            pre.next = cur1 if cur1 else cur2
            return prehead.next
        
        def merge_sort(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None # 注意遍历到 tail 时要断开链表
                return head
            
            fast = head
            slow = head
            while fast != tail and fast.next != tail:
                slow = slow.next
                fast = fast.next.next
            
            left = merge_sort(head, slow)
            right = merge_sort(slow, tail)
            return mergeList(left, right)

        return merge_sort(head, None)

# 细节还是很多的
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 合并链表，要返回合并后的 head 和 tail
        def mergeList(head1, head2):
            prehead = ListNode(-1)
            pre = prehead
            cur1 = head1
            cur2 = head2
            while cur1 and cur2:
                if cur1.val <= cur2.val:
                    pre.next = cur1
                    cur1 = cur1.next
                else:
                    pre.next = cur2
                    cur2 = cur2.next
                pre = pre.next
            pre.next = cur1 if cur1 else cur2
            while pre.next:
                pre = pre.next
            return prehead.next, pre 
        
        def getlenght(head) -> int:
            cur = head
            ans = 0
            while cur:
                cur = cur.next
                ans += 1
            return ans
        # 分割 head 链表的第 k 个节点，返回分割后的头
        def split(head, k) -> ListNode: 
            # 这里不能复用 getlength，否则会导致 logN 退化为 N2 
            # length = getlenght(head)
            cur = head        
            for _ in range(k - 1):
                if cur == None:
                    return None
                cur = cur.next
            if not cur or not cur.next:
                return None
            tmp = cur.next
            cur.next = None
            return tmp
        # 倍增法实现迭代归并排序
        prehead = ListNode(next=head)
        step = 1
        length = getlenght(head)
        while step < length:
            pre = prehead # 记录需要合并链表的 pre
            cur = prehead.next
            while cur:
                head1 = cur # 两个 head 是切下来的两个 list
                head2 = split(head1, step)
                cur = split(head2, step) # cur 是合并后的 next
                newhead, newtail = mergeList(head1, head2)
                # print(newhead, newtail, step, cur)
                pre.next = newhead 
                newtail.next = cur 
                pre = newtail # pre 编程 merge 后的 tail
            step *= 2 # 倍增
        return prehead.next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergeList(head1, head2):
            prehead = ListNode(-1)
            pre = prehead
            cur1 = head1
            cur2 = head2
            while cur1 and cur2:
                if cur1.val <= cur2.val:
                    pre.next = cur1
                    cur1 = cur1.next
                else:
                    pre.next = cur2
                    cur2 = cur2.next
                pre = pre.next
            pre.next = cur1 if cur1 else cur2
            while pre.next:
                pre = pre.next
            return prehead.next
        # 倍增法
        n = len(lists)
        step = 1
        while step < n:
            for i in range(0, n - step, step * 2):
                lists[i] = mergeList(lists[i], lists[i + step])
            step *= 2
        return lists[0] if lists else None

class Node:
    def __init__(self, key=0, value=0, pre=None, next=None):
        self.key = key
        self.value = value
        self.pre = pre
        self.next = next
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # 双向链表哑节点一定在固定的 head
        # 则 dummy.pre 就是 tail 节点
        self.dummy = Node()
        self.dummy.next = self.dummy
        self.dummy.pre = self.dummy
        self.map = defaultdict(lambda : -1)

    # 将 node 挪到链表头
    # 注意不管是挪节点还是 remove，都只对指针操作，创建节点在 put 中
    def node_front(self, node):
        if node == None:
            return
        node.pre = self.dummy
        node.next = self.dummy.next
        node.next.pre = node
        node.pre.next = node

    # 删去 node
    def remove(self, node):
        node.pre.next = node.next
        node.next.pre = node.pre

    # 用 map 查找节点是否在链表中，同时要注意维护 map
    # 如何有，则将其挪到最前
    def get_node(self, key):
        if self.map[key] == -1:
            del self.map[key]
            return None
        node = self.map[key]
        self.remove(node)
        self.node_front(node)
        return node
    # 用 get_node 返回 value
    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1
    # 如果当前节点已经在链表中，相当于查找更新并
    # 否则相当于添加节点，则需要维护 map
    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
        else:
            new_node = Node()
            new_node.value = value
            new_node.key = key
            self.map[key] = new_node
            self.node_front(new_node)
            if len(self.map) > self.capacity:
                last_node = self.dummy.pre
                del self.map[last_node.key]
                self.remove(last_node)

# 别忘了怎么构建 TreeNode 就行
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node):
            if node == None:
                return node
            dfs(node.left)
            ans.append(node.val)
            dfs(node.right)
        dfs(root)
        return ans

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        queue = deque()
        queue.append(root)
        ans = 0
        while queue:
            ans += 1
            k = len(queue)
            for i in range(k):
                tmp = queue[0]
                queue.popleft()
                if tmp.left:
                    queue.append(tmp.left)
                if tmp.right:
                    queue.append(tmp.right)
        return ans

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        def dfs(node):
            if not node:
                return
            node.left, node.right = node.right, node.left
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return root

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        def check(l, r):
            if not l and not r: # 到叶子了
                return True
            if not l or not r or l.val != r.val:
                return False
            return check(l.left, r.right) and check(l.right, r.left)
        return check(root.left, root.right)

# 把下面两个写在一个函数就是一轮遍历
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        m = defaultdict(int)
        def depth(node):
            if not node:
                m[node] = 0
                return 0
            de = max(depth(node.left), depth(node.right)) + 1
            m[node] = de
            return de   
        depth(root)
        # print(m)
        ans = 0
        def dfs(node):
            nonlocal ans
            if not node:
                return
            ans = max(ans, m[node.left] + m[node.right])
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ans 

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None:
            return []
        queue = deque()
        queue.append(root)
        ans = []
        while queue:
            k = len(queue)
            res = []
            for i in range(k):
                tmp = queue[0]
                res.append(tmp.val)
                queue.popleft()
                if tmp.left:
                    queue.append(tmp.left)
                if tmp.right:
                    queue.append(tmp.right)
            ans.append(res)
        return ans

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        if n == 0:
            return None
        def dfs(l, r):
            nonlocal nums
            if l > r:
                return None
            mid = l + r >> 1
            node = TreeNode(nums[mid])
            node.left = dfs(l, mid - 1)
            node.right = dfs(mid + 1, r)
            return node
        return dfs(0, n - 1)