二叉树

1、前序遍历

根 -> 左 -> 右

递归：root.val + func(root.left) + func(root.right)
迭代: [root] -> stack.pop -> root.right -> root.left

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 1、递归
        if not root:
            return self.res
        
        self.res.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        
        return self.res

        
        # 2、迭代
        if not root:
            return []
        
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            
        return res

2、中序遍历

左 -> 根 -> 右

递归：func(root.left) + root.val + func(root.right)
迭代: 指针滑动，找出所有左子树，pop，保存tmp.val, 赋值右子树

class Solution:
    def __init__(self):
        self.value = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 1、递归
        if not root:
            return self.value
        
        self.inorderTraversal(root.left)
        self.value.append(root.val)
        self.inorderTraversal(root.right)
        
        return self.value
        
        # 2、迭代
        res = []
        stack = []
        p = root
        while stack or p:
            while p:
                stack.append(p)
                p = p.left
            tmp = stack.pop()
            print(tmp)
            res.append(tmp.val)
            p = tmp.right
        
        return res

3、后序遍历

左 -> 右 -> 根

递归：root.val + func(root.right) + func(root.left) 然后反转

迭代: [root] -> stack.pop -> root.left -> root.right

class Solution:
    def __init__(self):
        self.res = []
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 1、递归
        if not root:
            return self.res
        
        self.postorderTraversal(root.left)
        self.postorderTraversal(root.right)
        self.res.append(root.val)
        
        return self.res
        
        # 2、迭代
        if not root:
            return []
        
        tmp = []
        stack = [root]
        while stack:
            item = stack.pop()
            tmp.append(item.val)
            if item.left:
                stack.append(item.left)
                
            if item.right:
                stack.append(item.right)
        
        return tmp[::-1]

4、BFS广度遍历(层次遍历)

[root] -> [root.left, root.right] -> [tmp.val]

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        res = []
        cur = [root]
        while cur:
            tmp = []
            next_cur = []
            for i in cur:
                tmp.append(i.val)
                if i.left:
                    next_cur.append(i.left)
                if i.right:
                    next_cur.append(i.right)
            res.append(tmp)
            cur = next_cur
        
        return res

快速排序

def sort(lst):
    def partition(arr, left, right):
        key = left
        while(left<right):
            while left < right and arr[right] >= arr[key]:
                right -= 1
            while left < right and arr[left] <= arr[key]:
                left += 1

            (arr[left], arr[right]) = (arr[right], arr[left])

        (arr[left], arr[key]) = (arr[key], arr[left])
        return left

    def quicksort(arr, left, right):
        if left >= right:
            return
        mid = partition(arr, left, right)
        quicksort(arr, left, mid-1)
        quicksort(arr, mid+1, right)

    n = len(lst)
    if n <= 1:
        return lst
    quicksort(lst, 0, n - 1)
    return lst

双指针

1、快慢指针

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

(1)、判定链表中是否含有环

单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。
如果链表中不包含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环。
但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。
经典解法就是用两个指针，一个每次前进两步，一个每次前进一步。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

(2)、已知链表中含有环，返回这个环的起始位置

当快慢指针相遇时，让其中任一个指针重新指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。这是为什么呢？
第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，也就是说比 slow 多走了 k 步（也就是环的长度）
设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点，所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了

(3)、寻找链表中间位置

类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置

(4)、寻找链表的倒数第 k 个元素

我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）

2、左右指针

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

二分查找
两数之和（升序数组，找出两数和为目标数值的数）
反转数组
滑动窗口算法（这也许是双指针技巧的最高境界了，如果掌握了此算法，可以解决一大类子字符串匹配的问题）

排序算法

https://blog.csdn.net/weixin_41571493/article/details/81875088

1、交换排序

1.1 冒泡排序

顺序比较，每次比较相邻元素，满足条件不交换，不满足条件交换。（每次都会将最值放到队首（尾））
时间复杂度O(n^2)，空间复杂度O(1)

1.2 快速排序

选基准值，小的放左，大的放右，基准值将其分为两个分区
对两个分区递归的使用相同方法排序
时间复杂度O(nlogn)，空间复杂度O(logn)

2、插入排序

2.1 简单的插入排序

第一个元素开始，可以认为已经被排序
取出下一个元素，在已经排好序的前面的序列中从后向前扫描
如果扫描的元素大于取出的元素，则其向后移，直到扫描到等于或者小于其的位置，将其放入
重复上述步骤
时间复杂度O(n^2)，空间复杂度O(1)

2.2 希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
时间复杂度O(nlogn)，空间复杂度O(1)

3、选择排序

3.1 简单选择排序

对数据操作n-1轮，每轮找出一个最大（小）值。
操作指选择，即未排序数逐个比较交换，争夺最值位置，每轮将一个未排序位置上的数交换成已排序数，即每轮选一个最值
时间复杂度O(n^2)，空间复杂度O(1)

3.2 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)，空间复杂度O(1)

4、归并排序

4.1 二路归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
时间复杂度O(nlogn)