二叉树的各种遍历方式
1.二叉树的前序遍历（easy）
前序遍历就是头结点永远第一访问，接着是头结点的左孩子节点，右孩子节点；后序遍历就是左、右、头结点；中序遍历就是左、头结点、右；
所以只要一道题你搞懂了，三道题就是一道题
//这里是官方给出的js中二叉树的构造函数（只写一遍哈）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var preorderTraversal = function(root) {
let res = [];
let helper = function(root){
if(root === null) return;//如果是叶子节点，直接返回
res.push(root.val);//1.将根节点压入
helper(root.left);//2.递归遍历左子树，目的——>压入根节点的左子树的头结点
helper(root.right);//3.递归遍历右子树，目的——>压入根节点的右子树的头结点
}
helper(root);
return res;
};
2.二叉树的中序遍历（easy）
var preorderTraversal = function(root) {
let res = [];
let helper = function(root){
if(root === null) return;//如果是叶子节点，直接返回
helper(root.left);//1.递归遍历左子树
res.push(root.val);//2.将根节点压入
helper(root.right);//3.递归遍历右子树
}
helper(root);
return res;
};
3.二叉树的后序遍历(easy)
var preorderTraversal = function(root) {
let res = [];
let helper = function(root){
if(root === null) return;//如果是叶子节点，直接返回
helper(root.left);//1.递归遍历左子树
helper(root.right);//2.递归遍历右子树
res.push(root.val);//3.将根节点压入
}
helper(root);
return res;
};
4.二叉树的层序遍历（medium）
先给一下力扣官方的题目描述吧 ↓↓↓↓↓
层序遍历就是按照二叉树的结构，先遍历第一层（根节点）再遍历第二层，接着第三层……（还是看图吧，亲自手绘）
以下是我的图解
即结果输出要求，首先是第一层从左到右的节点，接着是第二层，第三层……，那这样改怎么做呢，显然，你用之前的递归是无法完成的，因为你递归是向深处遍历，纵向延伸，无法横向移动！
我们需要借助一个数据结构，队列，队列是先进先出表，你想啊，你每次遍历，先把节点压入队列中，只要队列中有东西，你就先遍历队列里面的，没有了我再接着遍历后面的，把后面一层的压入队列里面去，一直循环到没有节点为之，看代码上的详细注释
1. 层序遍历 I
var levelOrder = function(root) {
let res= [];
//定义一个队列，根据层次顺序保存节点
let queue = [root];
if(root === null) return res;
while(queue.length > 0){
//每次从队列中弹出一个节点，并放到res中去
let node = queue.shift();
res.push(node.val);
//检查弹出的节点，有没有子孩子，有就加入到队列中，这样就把下一层的节点顺序也安排的明明白白的
if(node.left !== null) queue.push(node.left);
if(node.right !== null) queue.push(node.right);
}
return res;
};
看完注释，如果还是不懂，来看看我的图趴
2. 层序遍历 I I（easy）（搞不懂为什么这个是easy，是因为变式I做出来了吗）
看一下官方题目描述 ↓↓↓↓↓
var levelOrder = function(root) {
let res = [];//存放最终的遍历结果
//定义一个队列，js中可以使用数组（shift和push方法）模仿一个队列
let queue = [];
//首先第一层，先把根节点放入队列，注意，这时候队列里面已经有东西了
if(root !== null) queue.push(root);
//遍历队列里面的节点
while(queue.length > 0){//只要队列的长度大于0，就一直循环遍历
//注意，这里需要定义这个队列的长度n，不然队列的长度就是动态变化了哦
let n = queue.length;
//定义层级，即level是保存每一层的节点
let level = [];
//n是当前层的最大节点数量
for(let i = 0;i < n;i ++){
//从队列头中取出一个节点
let node = queue.shift();
//将取出的节点的值压入当前层level
level.push(node.val);
//看看取出的这个节点有没有左右子孩子，有就压入到队列里面去
//所以上面必须有一个n，每一层数量应该是确定好的，而下一层的节点数量也会在这一层遍历完之后确定好
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
//将当前层的节点作为一个整体压入结果中
res.push(level);
}
return res;
};
3. 层序遍历 I I I（锯齿形层序遍历）
官方题目描述 ↓↓↓↓↓
其实变式三，就是变式二的一点小改动，每次压入当前层节点的位置不一样而已，奇数从队列的尾插入，偶数从队列头插入，而队列是在头部先进先出（一般），所以，每次出队列的顺序就会按奇偶而不同了
var levelOrder = function(root) {
let count = 0;
let ans = [];
let res = [];
let queue = [root];
if(root === null) return res;
while(queue.length > 0){
count ++;//控制层数，遍历完一层，层数加一
level = [];
let len = queue.length;
for(let i = 0;i < len;i ++){
let node = queue.shift();
//偶数层，从头部依次加入队列，这样，出队列就是最后一个进的先出队列
//牢记unshift()方法是从数组第一个元素之前开始添加元素，即新添加的元素是数组的第一个元素
if(count % 2 === 0) level.unshift(node.val);
//奇数层，从队列尾部压入，这样，出队列就是正常顺序，从左向右
else level.push(node.val);
if(node.left !== null) queue.push(node.left);
if(node.right !== null) queue.push(node.right);
}
res.push(level);
}
return res;
};
ok，今天就到这里了，感谢浏览，码字不易，不介意的话，给个一键三连再走呗 ヾ(?°?°?)ﾉﾞ