一、前言
Medium 难度次要考查联合二叉树性质的 CRUD 操作，而这所有的根底都离不开遍历二叉树。
二叉树是图的子集，因此同样实用以下两种搜寻思维：
- DFS（深度优先搜寻）：沿着根节点递归上来，遇到叶子节点则向上回溯；
- BFS (广度优先搜寻)：依照二叉树的档次拜访，通常采纳队列保留每个档次的节点。
因为二叉树自身的定义就是递归的，所以采纳递归解决起来，代码更容易了解。然而递归的效率绝对比较慢，次要起因在于：一个函数被调用的工夫和空间老本开销很大，递归太多很可能导致调用栈溢出的问题。上一篇中也提到能够采纳尾递归的书写形式，让 JavaScript 引擎去将递归优化成迭代，从而解决性能上的问题。
然而在一些状况下，尾递归并没有那么好写，所以本文会同时给出递归和迭代的解决方案。
接下来，通过具体的题目解析，带大家理解 DFS 和 BFS 搜寻思维在二叉树中的利用。
二、102. 二叉树的档次遍历
给定一个二叉树，返回其按档次遍历的节点值。（即逐层地，从左到右拜访所有节点）。
1、BFS
这道题目要求按档次遍历节点，很合乎 BFS 搜寻思维的定义，所以代码也很好了解。
这里须要 利用队列（queue）来保留每一层须要拜访的节点 ，须要特地留神队列的个性是 先进先出，而本题要求每一层从左到右遍历，所以须要先将左子树放入队列。
2、DFS
采纳 DFS 搜寻思维，须要留神在 递归的过程中记录以后节点的档次信息：
三、145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
二叉树中最常见的就是依照根节点拜访秩序定义的三种遍历形式：
- 先序遍历：首先拜访根，再先序遍历遍历左子树，最初先序遍历右子树；
- 中序遍历：首先中序遍历左子树，再拜访根，最初中序遍历右子树；
- 后序遍历：首先后序遍历左子树，再后序遍历右子树，最初拜访根；
以本道题的后序遍历为例，尝试递归和迭代两种不同的办法：
1、递归实现 DFS
从定义中，大家应该可能设想到递归的代码如何书写：
参考视频：传送门
2、迭代实现 DFS
本道题目采纳迭代实现 DFS 不太容易了解，次要因为迭代不能像递归那样向上回溯，所以迭代向下遍历的过程中，无奈保障根节点最初拜访。
再回顾一下后序遍历最终失去的序列：
左子树 --> 右子树 --> 根如果必须先拜访根节点，那么是不是能够失去这样的序列：
根 --> 右子树 --> 左子树最初，再将该序列反转，是不是就是本题所要求解的后序遍历！
这里咱们利用栈 后进先出 的个性，将右子树最初推动栈，使得右子树先进行深度搜寻：
四、987. 二叉树的垂序遍历
给定二叉树，按垂序遍历返回其结点值。对位于 (X, Y) 的每个结点而言，其左右子结点别离位于 (X-1, Y-1) 和 (X+1, Y-1)。把一条垂线从 X = -infinity 挪动到 X = +infinity，每当该垂线与结点接触时，咱们按从上到下的程序报告结点的值（Y 坐标递加）。如果两个结点地位雷同，则首先报告的结点值较小。按 X 坐标程序返回非空报告的列表。每个报告都有一个结点值列表。
最初，通过本道题目来开启 Medium 难度题型的解说。
这道题目要求咱们求出垂序遍历序列，那么首先还是得先遍历二叉树，这里采纳递归实现 DFS 来遍历二叉树。
在递归的过程中须要向下传递坐标信息，并且通过 HashTable 记录各个节点的三元组信息（x 坐标、y 坐标，节点值），以便后续结构垂序序列：
失去坐标之后，须要对三元组进行综合排序，最初再依据 x 坐标结构垂序遍历序列，工夫复杂度 O(nlogn)。
写在最初
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。
本系列文章会别离给出一种算法的 3 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主。