一、前言
本难度的题目主要考察二叉树的基本概念和操作。
1、基本概念
树是计算机科学中经常用到的一种非线性数据结构，以分层的形式存储数据。二叉树是一种特殊的树结构，每个节点最多有两个子树，通常子树被称作“左子树”和“右子树”。
在这里插入图片描述以上述图片为例，介绍二叉树相关的几个术语：
- 节点的度：节点拥有子树的数量，图中节点 7 的度为 2；
- 叶子节点：度为 0 的节点，图中节点 2 就是一个叶子节点；
- 节点的层次：根节点的层定义为 1，根的孩子为第二层节点，依次类推；
- 树的深度：树中的最大节点层，图中树的深度为 3；
在 JavaScript 中，可以创建 TreeNode 对象来描述树的节点：
代码语言：text复制function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}另外二叉树也有不同的表现形态，最常见的就是二叉查找树（Binary Search Tree）,它具有以下性质：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
二叉查找树相比较其他数据结构的优势在于查找、插入的时间复杂度较低，为 O(logn)，并且对它进行中序遍历操作之后，可以得到一个有序序列，这使得它成为出题的常客。
2、基本操作
二叉树经常考察的问题主要基于以下操作：
- 计算二叉树的深度；
- 先序遍历：首先访问根，再先序遍历遍历左子树，最后先序遍历右子树；
- 中序遍历：首先中序遍历左子树，再访问根，最后中序遍历右子树；
- 后序遍历：首先后序遍历左子树，再后序遍历右子树，最后访问根；
- 层次遍历：按照节点的层次访问；
二叉树非常适合采用递归思想处理，虽然递归非常耗费内存，但是它写出的代码可读性非常强，另外可以通过尾递归的书写方式，让 JavaScript 引擎将其优化为迭代的方式，从而大幅度地优化时间和空间的复杂度。
二、104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
这是一道计算二叉树深度的题目，利用递归思想：不断计算子树的深度，即可得到整个二叉树的深度。
在这里插入图片描述相同类型的题目：
- 【111. 二叉树的最小深度】；
三、144. 二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
采用递归实现二叉树的前序遍历的代码，可读性非常强：
参考视频：传送门
在这里插入图片描述同样的实现中序遍历以及后序遍历，是不是小菜一碟!
四、783. 二叉搜索树结点最小距离
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
解题思路：二叉搜索树的中序遍历序列为递增序列；
在这里插入图片描述相同类型的题目：
- 【530. 二叉搜索树的最小绝对差】；
- 【897. 递增顺序查找树】；
- 【653. 两数之和 IV - 输入 BST】；
五、563. 二叉树的坡度
给定一个二叉树，计算整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。整个树的坡度就是其所有节点的坡度之和。
解题思路：在后序遍历的过程中，先计算左子树和值以及右子树和值，再计算当前节点的坡度，最后更新当前子树的和值。
在这里插入图片描述六、107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
1、队列和栈
第一种方法：采用栈和队列维护每一层访问的节点。
在这里插入图片描述2、递归
第二种方法：利用递归思想在前序遍历的过程中记录相应的层级。
在这里插入图片描述相同类型的题目：
- 【637. 二叉树的层平均值】；
- 【872. 叶子相似的树】；
七、938. 二叉搜索树的范围和
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。二叉搜索树保证具有唯一的值。
这道题目主要考察前文提到的二叉查找树的特性，处理的方式类似于上几篇提到的二分搜索算法：
在这里插入图片描述相同类型的题目：
- 【700. 二叉搜索树中的搜索】；
- 【669. 修剪二叉搜索树】；
- 【538. 把二叉搜索树转换为累加树】；
八、100. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
解题思路：递归处理两个树的根节点、左子树和右子树，如果它们都相等，那么两个树必然相等。
在这里插入图片描述相同类型的题目：
- 【572. 另一个树的子树】；
- 【101. 对称二叉树】；
- 【226. 翻转二叉树】；
写在最后
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。
本系列文章会分别给出一种算法的3种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。
