Array 数组

[x] 485：Max Consecutive Ones
[x] 283：Move Zeros
[x] 27：Remove Element

Hint：基本都是双指针类型，要么一快一慢，要么一头一尾。

LinkedList 链表

[x] 203：Remove Linked List Elements

Hint：尝试添加虚拟（临时、dummy）节点使链表永不为空、永不无头，简化插入和删除。
[x] 206：Reverse Linked List

Queue 队列

[x] 933：Number of Recent Calls

Hint：请求不断进入，只要看队首满不满足要求即可。

Stack 栈

[x] 20：Valid Parentheses
[x] 496：Next Great Element I

Hint：用到了哈希表和单调栈，如果要求不能暴力解，这题应该算Medium。

Hash Table 哈希表

[x] 217：Contains Duplicate
[x] 389：Find the difference
[x] 496：Next Great Element I

Set 集合

[x] 217：Contains Duplicate
[x] 705：Design Hashset

705 Hint：设计题！

简单做法：直接用数组来做，其索引作为key，bool类型值作为value。

复杂做法：使用散列函数，并在哈希碰撞处使用链表解决。（链地址法）

哈希函数的共同特点是使用模运算符：hash = value mod base。base的选择是空间和碰撞之间的权衡，且常选择质数。

该题提前已知总操作数有10000，那么base可以选择769，使用链表（借用python的deque）解决冲突时，这样平均下来具有冲突的链表最多只需要存14个数。（即一个长度为769大小的列表，列表中的元素为链表）。

如此，该Hashset的访问、插入和删除元素时间复杂度为 $O(\dfrac{n}{\text{base}})$ 。（最坏情况下需要遍历某支链表）

Tree 树

对于遍历树节点的做法主要有三种：

使用递归法（DFS），模板基本定型，容易理解。

时间： $O(n)$ ；空间： $O(\log n)$ ，最差 $O(n)$ 。
使用迭代法，比较考验对数的理解能力，相当于把递归栈给显式的编写出来。

时间： $O(n)$ ；空间： $O(\log n)$ ，最差 $O(n)$ 。
使用Morris遍历（有点中序线索二叉树的感觉，不过可以用来遍历二叉树，改变打印位置或增加其他规则即可实现不同的遍历次序）（超强进阶算法）。

时间： $O(n)$ ；空间： $O(1)$ 。

另外，还有线索二叉树（Threaded BinaryTree），利用了二叉树中的空指针域来存放在某种遍历次序下的前驱和后继。根据遍历次序的不同，线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树。

前序遍历

[x] 144：Binary Tree Preorder Traversal

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        res = list()
        dfs(root)
        return res

一路向左，没有才右~
栈用来存放每次遍历到的节点，为后续探索留退路（栈里面的节点是后续探索节点的祖先）；
一旦“祖先”出场指引前往右子树的方向，祖先就得出栈（小祖先帮不了忙，再请大祖先出场）。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return
        
        node = root
        stack = list()
        
        while node:
            res.append(node.val)
            stack.append(node)
            node = node.left
            while not node and stack:
                node = stack.pop()
                node = node.right
        return res

这个方法有中序线索二叉树的味道，利用线索实现回到父节点的能力。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return res
        
        p = root
        while p:
            if not p.left:
                res.append(p.val)
                p = p.right
            else:
                pre = p.left
                while pre.right and pre.right != p:
                    pre = pre.right
                if not pre.right:                
                    pre.right = p
                    res.append(p.val)
                    p = p.left
                else:
                    pre.right = None
                    p = p.right
        return res

中序遍历

[x] 94：Binary Tree Inorder Traversal

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        res = list()
        dfs(root)
        return res

一路向左，没有才右~
跟迭代法前序遍历的区别在于访问节点的顺序不同。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return res
        
        node = root
        stack = list()
        while node:
            stack.append(node)
            node = node.left
            while not node and stack:
                node = stack.pop()
                res.append(node.val)
                node = node.right
        return res

跟Morris法前序遍历的区别在于访问节点的顺序不同。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return res
        
        p = root
        while p:
            if not p.left:
                res.append(p.val)
                p = p.right
            else:
                pre = p.left
                while pre.right and pre.right != p:
                    pre = pre.right
                if not pre.right:
                    pre.right = p
                    p = p.left
                else:
                    pre.right = None
                    res.append(p.val)
                    p = p.right
        return res

后序遍历

[x] 145：Binary Tree Postorder Traversal

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root):
            if not root:
                return root
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
            
        res = list()
        dfs(root)
        return res

一路向左，没有才右~
祖先出栈指引右子树方向时，如果存在右子树，祖先还得入栈；
需要pre来告诉父节点：右子树是否已经走过；如果走过，才访问该父节点，形成“左-右-根”的访问顺序。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return res
        
        stack = list()
        pre = None
        node = root
        while node:
            stack.append(node)
            node = node.left
            while not node and stack:
                node = stack.pop()
                if not node.right or node.right == pre:
                    res.append(node.val)
                    pre = node
                    node = None
                else:
                    stack.append(node)
                    node = node.right
        return res

这里需要记录从【当前节点的左孩子】到【当前节点在中序遍历下的前驱节点】的路径，一条“向右斜”的路径，将该路径中节点的value倒序输出，就是一段所要求的结果；
什么时候开始记录？当将线索断开的时候开始记录，因为线索是从左向右逐渐断开的；
最后一次记录什么？最后会只剩最右分支没有记录，因此需要记录从【根节点】到【最右节点】的路径；

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def addPath(node: TreeNode):
            count = 0
            while node:
                count += 1
                res.append(node.val)
                node = node.right
            res[(len(res)-count):] = res[-1:-count-1:-1] # 将新增节点的val倒序输出
#             i, j = len(res) - count, len(res) - 1
#             while i < j:
#                 res[i], res[j] = res[j], res[i]
#                 i += 1
#                 j -= 1
            
        res = list()
        if not root:
            return res
        
        p = root
        while p:
            if not p.left:
                p = p.right
            else:
                pre = p.left
                while pre.right and pre.right != p:
                    pre = pre.right
                if not pre.right:
                    pre.right = p
                    p = p.left
                else:
                    pre.right = None
                    addPath(p.left)
                    p = p.right
                    
        addPath(root)
        
        return res

Heap 堆

Topk Numbers

[x] 215：kth Largest Element in an Array

对于Top k问题，可以建立长度为k的最小堆（小根堆）。遍历完Array之后，堆的头节点即为要求的kth Largest Element。

因此，需要掌握【建堆】、【调整】和【删除】操作。

使用最大堆做法（堆排序）来求解。

时间： $O(n+(k-1)\log n)=O(n+k\log n)$ ，建堆是 $O(n)$ ，有 $k-1$ 次删除操作，每次删除是 $O(\log n)$ ；

空间： $O(\log n)$ ，主要是递归栈的空间代价。
使用最小堆做法来求解。

时间： $O(k+(n-k)\log k)$ ，建堆是 $O(k)$ ，有 $n-k$ 次删除操作，每次删除是 $O(\log k)$ ；

空间： $O(k)$ 。

原地建最大堆，同时删除前k-1个最大值；
那么，最后剩下的堆顶元素就是所要的第k个最大值；

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def buildMaxHeap(nums, heapSize):
            num_root = heapSize - (heapSize + 1) // 2 # 从倒数第一个非叶子节点开始遍历
            while num_root:
                ind_node = num_root - 1
                maxHeapify(nums, ind_node, heapSize)
                num_root = num_root - 1
                
        def maxHeapify(nums, ind_node, heapSize):
            ind_l = ind_node * 2 + 1
            ind_r = ind_node * 2 + 2
            ind_largest = ind_node
            
            if ind_l < heapSize and nums[ind_l] > nums[ind_largest]: # 跟左孩子比较
                ind_largest = ind_l
            if ind_r < heapSize and nums[ind_r] > nums[ind_largest]: #跟右孩子比较
                ind_largest = ind_r
            if ind_largest != ind_node: # 当最大值位置不是node处时（最大值位置是处于孩子处）
                nums[ind_node], nums[ind_largest] = nums[ind_largest], nums[ind_node] # 交换位置
                maxHeapify(nums, ind_largest, heapSize) # 因为是在最大值的位置进行交换，那么就继续从最大值位置往下探索（递归）
                
        buildMaxHeap(nums, len(nums)) # 最大堆
        # print(nums)
        
        # 删除k-1次根节点
        for i in range(1, k):
            nums[0] = nums.pop() # 将最后一个节点移至根节点位置
            maxHeapify(nums, 0, len(nums))
            # print(nums)
        return nums[0]

只要维护一个大小为k的最小堆，当每次遇到比堆顶大的数时，则将堆顶的val更新为该数；
当遍历完array时，该最小堆的堆顶元素（最小元素）就是array中的第k个最大值；

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def buildMinHeap(heap):
            num_root = len(heap) - (len(heap) + 1) // 2
            while num_root:
                ind_root = num_root - 1
                minHeapify(heap, ind_root)
                num_root = num_root - 1
            
        def minHeapify(heap, ind_node):
            heapSize = len(heap)
            ind_l = ind_node * 2 + 1
            ind_r = ind_node * 2 + 2
            ind_smallest = ind_node
            if ind_l < heapSize and heap[ind_l] < heap[ind_smallest]:
                ind_smallest = ind_l
            if ind_r < heapSize and heap[ind_r] < heap[ind_smallest]:
                ind_smallest = ind_r
            if ind_smallest != ind_node:
                heap[ind_node], heap[ind_smallest] = heap[ind_smallest], heap[ind_node]
                minHeapify(heap, ind_smallest)
        
        if not nums:
            return []
        
        heap = list()
        heap = nums[0:k]
        buildMinHeap(heap) # 取nums的前k个元素建最小堆
        ind_num = k
        for i in range(k, len(nums)): # 从nums的第k+1个元素开始遍历
            val = nums[i]
            if val > heap[0]: # 当遇到比最小堆堆顶大的数时
                heap[0] = val # 更新堆顶的val
                minHeapify(heap, 0) # 并重新进行最小堆化
                
        return heap[0]