Week3基础知识

二叉树

二叉树、二叉查找树。基本操作是遍历查找、插入和删除。

遍历

前序、中序、后序、层次；
序列化和反序列化；
树上两个节点的距离；

二叉查找树

中序遍历序列有序！！！！如果不知道要怎么直接用树来解决，可以转成有序数组来做。

二叉查找树的查找操是常考的。

值得反复刷的题目：将有序数组转换为二叉搜索树、二叉搜索树迭代器

二叉树递归遍历

递归是处理二叉树问题常用的手段。尤其是在Depth维度上处理问题的时候。这周大部分题目也都是用递归来解决的。

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

三要素：

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

前序、中序、后序递归遍历的模板：这个太重要了，不然大部分二叉树的题都做不了。
144.二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(root, res):
            if not root: return

            res.append(root.val)
            preorder(root.left, res)
            preorder(root.right, res)
        
        res = []
        preorder(root, res)
        return res

二叉树的后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root, res):
            if not root: return

            postorder(root.left, res)
            postorder(root.right, res)
            res.append(root.val)

        res = []
        postorder(root, res)
        return res

二叉树的中序遍历

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

递归值得反复刷的题：平衡二叉树、前中后序遍历、相同的树、翻转二叉树、最近公共祖先

搜索

额外补一下Tree BFS和DFS，其实就是树的两种遍历搜索方式。

广度优先搜索

可遍历一个树并使用一个队列来跟踪一个层级的所有节点，之后再跳转到下一个层级。任何涉及到以逐层级方式遍历树的问题都可以使用这种方法有效解决。

BFS 模式的工作方式是：将根节点推至队列，然后连续迭代直到队列为空。在每次迭代中，我们移除队列头部的节点并访问该节点。在移除了队列中的每个节点之后，我们还将其所有子节点插入到队列中。

如何识别 BFS 模式：

如果你被要求以逐层级方式遍历（或按层级顺序遍历）一个树。

二叉树BFS值得反复刷的题目：序列化和反序列化

深度优先搜索

使用递归（或该迭代方法的技术栈）来在遍历期间保持对所有之前的（父）节点的跟踪。

DFS 模式的工作方式是从树的根部开始，如果这个节点不是一个叶节点，则需要做两件事：

决定现在是处理当前的节点（pre-order），或是在处理两个子节点之间（in-order），还是在处理两个子节点之后（post-order）
为当前节点的两个子节点执行两次递归调用以处理它们

如何识别 DFS 模式：

如果你被要求用 in-order、pre-order 或 post-order DFS 来遍历一个树
如果问题需要搜索其中节点更接近叶节点的东西

DFS 模式的问题：路径系列、二叉树中所有距离为 K 的结点

堆

第一周其实就有接触堆：大根堆和小根堆。感觉堆的题目还是比较直观的。

面试还是要掌握手写数组构造大根堆和小根堆，贴个自己实现代码！

数据流的中位数这个题目可是太经典了，以后多刷。

Week3总结回顾

这周周赛的难度感觉比前两周要低一些。test cases也比较好想。主要是第四题做的有点僵硬。。以为要递归去计算两个子树的值（想到了二叉树中所有距离为 K 的结点那道题目，就用类似的findParents方法去做了）。实际计算一个子树就可以了。。还是做的有些急，写代码之前没有考虑清楚，写了一个小时错误的思路，导致最后没有推倒重来的时间了。
最近一周因为面试和毕业的事情忙了四天，最后两天抽空补了一下落下的进度。今天周赛确实不如前两次注意力那么集中。看来每天做题除了扩充知识储备，状态影响也蛮大的。
每周一提醒：做题需要明确时间复杂度！！！
二叉树题目想看自己解法的最差时间复杂度，可以看看在一个单链树上的时间复杂度。