一、前言
本难度的题目次要考查二叉树的基本概念和操作。
1、基本概念
树是计算机科学中常常用到的一种非线性数据结构，以分层的模式存储数据。二叉树是一种非凡的树结构，每个节点最多有两个子树，通常子树被称作“左子树”和“右子树”。
以上述图片为例，介绍二叉树相干的几个术语：
- 节点的度 ：节点领有子树的数量，图中节点 7 的度为 2；
- 叶子节点 ：度为 0 的节点，图中节点 2 就是一个叶子节点；
- 节点的档次 ：根节点的层定义为 1，根的孩子为第二层节点，顺次类推；
- 树的深度 ：树中的最大节点层，图中树的深度为 3；
在 JavaScript 中，能够创立 TreeNode 对象来形容树的节点：
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 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主。