1
class Solution:
2
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
3
        ans = 0
4

5
        def dfs(cur) -> int:
6
            nonlocal ans
7
            if cur is None:
8
                return 0
9
            l = dfs(cur.left) + 1
10
            r = dfs(cur.right) + 1
11
            nonlocal ans
12
            ans = max(ans, l + r - 2)
13
            return max(l, r)
14

15
        dfs(root)
16
        return ans

1
class Solution:
2
    def isSame(self, p, q) -> bool:
3
        if p is None or q is None:
4
            return p is q
5
        if p.val != q.val:
6
            return False
7
        return self.isSame(p.left, q.right) and self.isSame(p.right, q.left)
8

9
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
10
        return self.isSame(root.left, root.right)

1
class Solution:
2
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
3
        if root is None:
4
            return None
5
        tmp = deepcopy(root.right)
6
        root.right = self.invertTree(root.left)
7
        root.left = self.invertTree(tmp)
8
        return root

1
class Solution:
2
    def maxDepth(self, root: Optional[TreeNode]) -> int:
3
        if root is None:
4
            return 0
5
        return max(self.maxDepth(root.left) + 1, self.maxDepth(root.right) + 1)

1
class Solution:
2
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3
        ans = []
4

5
        def dfs(cur):
6
            if cur is None:
7
                return
8
            dfs(cur.left)
9
            ans.append(cur.val)
10
            dfs(cur.right)
11

12
        dfs(root)
13

14
        return ans

1
class LRUCache:
2

3
    def __init__(self, capacity: int):
4
        self.capacity = capacity
5
        self.cache = OrderedDict()
6

7
    def get(self, key: int) -> int:
8
        if key not in self.cache:
9
            return -1
10
        self.cache.move_to_end(key, last=False)
11
        return self.cache[key]
12

13
    def put(self, key: int, value: int) -> None:
14
        self.cache[key] = value
15
        self.cache.move_to_end(key, last=False)
16
        if len(self.cache) > self.capacity:
17
            self.cache.popitem()

1
class Solution:
2
    def mergeTwo(self, left: Optional[ListNode], right: Optional[ListNode]) -> Optional[ListNode]:
3
        dummy = ListNode()
4
        cur = dummy
5

6
        while left and right:
7
            if left.val < right.val:
8
                cur.next = left
9
                left = left.next
10
            else:
11
                cur.next = right
12
                right = right.next
13
            cur = cur.next
14
        cur.next = left if left else right
15

16
        return dummy.next
17

18
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
19
        k = len(lists)
20
        if k == 0:
21
            return None
22
        if k == 1:
23
            return lists[0]
24
        left = self.mergeKLists(lists[: k // 2])
25
        right = self.mergeKLists(lists[k // 2 :])
26
        return self.mergeTwo(left, right)

1
class Solution:
2
    def get_middle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        if head is None:
4
            return None
5

6
        slow = head
7
        fast = head
8
        while fast.next and fast.next.next:
9
            fast = fast.next.next
10
            slow = slow.next
11

12
        res = slow.next
13
        slow.next = None
14
        return res
15

16
    def mergeTwo(self, left: Optional[ListNode], right: Optional[ListNode]) -> Optional[ListNode]:
17
        dummy = ListNode()
18
        cur = dummy
19

20
        while left and right:
21
            if left.val < right.val:
22
                cur.next = left
23
                left = left.next
24
            else:
25
                cur.next = right
26
                right = right.next
27
            cur = cur.next
28
        cur.next = left if left else right
29

30
        return dummy.next
31

32

33
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
34
        if head is None or head.next is None:
35
            return head
36

37
        middle = self.get_middle(head)
38

39
        left = self.sortList(head)
40
        right = self.sortList(middle)
41

42
        return self.mergeTwo(left, right)

1
class Solution:
2
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
3
        cur = head
4
        while cur:
5
            cur.next = Node(cur.val, cur.next)
6
            cur = cur.next.next
7

8
        cur = head
9
        while cur:
10
            if cur.random:
11
                cur.next.random = cur.random.next
12
            cur = cur.next.next
13

14
        cur = dummy = Node(0, head)
15
        while cur.next:
16
            cur.next = cur.next.next
17
            cur = cur.next
18

19
        return dummy.next

1
class Solution:
2
    def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        prev = None
4
        cur = head
5
        while cur:
6
            nxt = cur.next
7
            cur.next = prev
8
            prev = cur
9
            cur = nxt
10
        return prev
11

12
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
13
        dummy = ListNode(0, head)
14

15
        cur = dummy.next
16
        cnt = 0
17
        cur_head = cur
18
        pre_cur_head = dummy
19
        while cur:
20
            cnt += 1
21
            nxt = cur.next
22
            if cnt >= 2:
23
                cur.next = None
24
                new_head = self.reverse(cur_head)
25
                cur_head.next = nxt
26
                pre_cur_head.next = new_head
27

28
                pre_cur_head = cur_head
29
                cur_head = nxt
30
                cnt = 0
31

32
            cur = nxt
33

34
        return dummy.next