二叉树基础知识：数据结构-二叉树
要了解二叉树，一定得了解二叉树的几种遍历方式：
在递归遍历二叉树时，我们应该明确以下 3 个步骤：
1. 确定递归的入参和返回结果
根据题目，我们需要先确定递归函数的入参是什么？简单分为以下情况：
-
第一种：入参只有当前根节点，每次递归的结果不影响下一次递归。如226. 翻转二叉树(简单)这道题目
-
第二种：如果要判断树是否对称/相等 等情况时，我们需要将左子树和右子树进行比较，那么入参一定至少有两个。分别对应左子树和右边子树。如：101. 对称二叉树(简单)
-
第三种：每一次递归需要依赖上一次递归的结果，那么每次递归的结果，需要被 return 出来。如：104. 二叉树的最大深度(简单)
-
第四种：递归时，需要通过参数来体现
回溯的思想。当探索的路径不满足条件时，需要返回上一步，走另外一条分支。如：257. 二叉树的所有路径(简单)、129. 求根节点到叶节点数字之和(中等)
2. 确定递归的终止条件
终止条件可以简单的分为三种：
- 第一种：判断当前节点是否存在，不存在则 return。如226. 翻转二叉树(简单)这道题目，由于需要对所有节点做处理。所以一直遍历到了空节点为止。
traversal(node) {
if (!node) {
return;
}
}- 第二种：如果题目中明确表示求相关叶子节点的信息，那么我们的退出条件应该到叶子节点即可，不让递归中出现空节点。如404. 左叶子之和(简单)、129. 求根节点到叶节点数字之和(中等)、257. 二叉树的所有路径(简单)。为了保证遍历中不存在空节点，我们在是否进行下一次递归时，也需要加上为空判断。如：
node.left && traversal(node.left);
traversal(node) {
if (node.left === null && node.right === null) {
return;
}
node.left && traversal(node.left);
node.right && traversal(node.right);
}第三种：当递归过程中，满足了要求条件时，需要立刻终止递归，返回当前结果。如：112. 路径总和(简单)
3. 编写递归函数的单层逻辑，确定下一次递归的入参
在做二叉树的迭代遍历之前，我们必须知道递归实际就是一种栈的结构实现，能用递归实现的逻辑，用栈一样能实现。
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
在迭代遍历二叉树，由于有中序和后序遍历，所以不能严格的按照"后进先出"的逻辑来做。我们需要加一个标志位，来判断该节点是否可以出栈并添加结果数组中。
层序遍历逻辑比较清晰，由于结果是按照先进先出的顺序弹出的。所以，我们利用队列来处理。
从根节点开始，逐层向下遍历。每一层遍历，按照先进先出的顺序，挨个弹出队头节点，再将队头节点的左右子节点也 push 到队列尾部。用作下一层遍历使用。以此循环，直到队列为空为止。
代码实现：二叉树的层序遍历(中等)
通过数组构建二叉树的题目中，如：106. 从中序与后序遍历序列构造二叉树(中等)、654. 最大二叉树(中等)，一定要想好递归的参数是什么？，在这里，我们的入参是一个数组区间。。每次递归时，根据这个数组区间，构建一颗子树，然后通过left,right属性将子树连接起来。同时我们还需要注意以下几点：
-
当需要“截取”数组，作为左子树和右子树时。不要通过
splice方法去将原数组截断修改，这会浪费一定的空间和时间。建议的做法是通过左右指针固定一个“区间”。在原数组的某个区间中，去做树的构建操作。 -
通过数组构建树时，结合第一步不改变原数组，也不生成新数组的前提下。递归方法的入参一般是左右指针。换一个说法，也可以说是，每一次递归构建树时，需要确定是从数组的哪个范围来构建。当左指针下标大于右指针下标时，退出递归
-
选出子树的根节点后，构建左子树和右子树时，注意不能取到中间节点。这和
二分法的取值类似。
二叉搜索树的一大特性就是：树的根节点的值一定大于其左子树所有节点，小于右子树的所有节点。如：98. 验证二叉搜索树(中等)
根据这个特性，我们在二叉搜索树查找某个节点的时间复杂度为 O(logn)。如：700.二叉搜索树中的搜索(简单)
同时，通过这个特性，我们也可以推断出：二叉搜索树的中序遍历，一定是一个递增的序列。在解决求第 k 大（小）的节点时，能很快得到结果。 如：230. 二叉搜索树中第 K 小的元素(中等)
在删除二叉搜索树的节点时，我们要注意保证二叉搜索树的特性。需要将删除节点的左子树的最大节点 或右子树的最小节点替换当前节点。如：450. 删除二叉搜索树中的节点(中等)