1.前言中等难度主要考察结合二叉树性质的CRUD操作，而这一切的基础都离不开遍历二叉树。二叉树是图的子集，所以下面两种搜索思路也适用：DFS（深度优先搜索）：沿着根节点递归向下，遇到叶子节点向上回溯；BFS（广度优先搜索）：按照二叉树的层级进行访问，通常用一个队列来保存每一层的节点。由于二叉树的定义本身就是递归的，递归处理后代码更容易理解。但是递归的效率比较慢。主要原因是一个函数被调用的时间和空间成本非常高，递归过多可能会导致调用栈溢出的问题。之前的文章也提到了尾递归的写法可以让JavaScript引擎把递归优化成迭代来解决性能问题。但是在某些情况下，尾递归并不是那么好写的，所以本文会同时给出递归和迭代的解决方案。下面通过分题分析，带大家了解DFS和BFS搜索思想在二叉树中的应用。2.102.二叉树的层次遍历给定一棵二叉树，返回其层次遍历的节点值。（即逐层，从左到右访问所有节点）。1.BFS本题要求分层遍历节点，符合BFS搜索思路的定义，所以代码通俗易懂。这里需要使用队列（queue）来保存每一层需要访问的节点。需要特别注意队列的特点是先进先出，而这道题需要每一层从左到右遍历，所以需要先将左子树放入队列。.2、DFS采用DFS搜索思想，在递归过程中需要注意记录当前节点的层级信息：3、145、二叉树的后序遍历给定一棵二叉树，返回其后序-顺序遍历。二叉树中最常见的是根据根节点访问顺序定义的三种遍历方式：前序遍历：先访问根，然后前序遍历遍历左子树，最后前序遍历到右子树；中序遍历：先中序遍历左子树，再访问根，最后中序遍历右子树；后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根；以这道题的后序遍历为例，尝试两种不同的递归和迭代方式：1.DFS的递归实现从定义上应该可以想象递归代码是怎么写的：参考视频：传送门2.DFS的迭代实现这个题目对于DFS的迭代实现不太容易理解，主要是因为迭代不能像递归那样往回走，所以在向下迭代遍历的过程中，不能保证最后访问到根节点。再回顾一下后序遍历最终得到的序列：左子树-->右子树-->根左子树最后再把序列倒过来，不就是本题要解的后序遍历吗！这里我们利用栈的后进先出特性，将右子树最后压入栈中，使得右子树在深度上优先搜索：4.987.一棵二叉树的垂直顺序遍历给定一棵二叉树，按垂直顺序遍历返回其节点值。对于(X,Y)处的每个节点，其左右子节点分别位于(X-1,Y-1)和(X+1,Y-1)。将垂直线从X=-infinity移动到X=+infinity，每次垂直线接触节点时，我们按从上到下的顺序（减少Y坐标）报告节点的值。如果两个节点的位置相同，则先报告的节点的值较小。返回X坐标顺序的非空报告列表。每个报告都有一个节点值列表。最后用这道题开始中等难度题型的讲解。这道题需要我们求出竖序遍历序列，所以还是要先遍历二叉树。这里采用DFS的递归实现来遍历二叉树。在递归的过程中，需要向下传递坐标信息，通过HashTable记录每个节点的三元组信息（x坐标，y坐标，节点值），以便后续构建垂直序列：得到坐标，需要对三元组进行综合排序，最后根据x坐标构造一个垂直顺序遍历序列，时间复杂度为O(nlogn)。写在最后算法是计算机的基础学科，用JavaScript刷一下也不丢人ε=ε=ε=┏(゜ロツ;)┛。本系列文章将总结算法的三种难度（简单难度、中等难度和困难难度）。简单难度会介绍算法的基础知识和实现，另外两个难度会重点讲解解题思路。如果本文对您有帮助，可以点赞或关注，鼓励博主。
