前端算法题：二叉树的遍历
二叉树基本概念
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
对于JavaScript来说，原生是没有二叉树这个数据结构的，所以需要自己来创建二叉树对象类来生成二叉树的结构，如下代码所示：
// 二叉树节点的构造函数
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
上面结构是一个二叉树的一个节点TreeNode类型的对象，每个节点有val表示当前的节点值，left和right表示左节点和右节点，他们分别又是新的TreeNode类型的对象，一个二叉树就是由若干个节点构成。其中，叶子结点：也称为终端结点，没有子树的结点。
由于二叉树本书并不是一个线性结构，不像数组我们可以很方便的用线性的数据结构来表示，对于二叉树而言，一般在代码中，我们能拿到的只是一个根节点的对象root，从根节点通过遍历来的得到完成的二叉树数据。
所以遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
遍历类型
由于二叉树每个节点有不同的方向，所以我们必须指定一个遍历的顺序，不同的遍历顺序得到的结果也不一样，所以一般分为前序遍历，中序遍历，后续遍历，层序遍历。
对于前序遍历，中序遍历，后续遍历而言，是以根节点为主，根在前表示前序，根在中间表示中序，根在后，表示后续，而左右两个节点按照左在前，右在后的顺序，所以，这三种遍历的方式他们的顺序分别是：
-
前序遍历：访问根结点->遍历左子树->遍历右子树 -
后续遍历：遍历左子树->遍历右子树->访问根结点 -
中序遍历：遍历左子树->访问根结点->遍历右子树
如下图二叉树：
-
前序遍历结果：0137849256 -
后续遍历结果：7839415620 -
中序遍历结果：7381940526
而层序遍历则更好理解，即从上往下一层一层遍历，每层按照从左往右遍历，因此上图的二叉树层序遍历结果就是：
-
层序遍历结果：0123456789
代码实现
对于二叉树这种结构，因为它的每个节点都有两个指向新的节点，所以我们很容易联想到使用递归来遍历一个二叉树，思路很简单，如下：
var loop = function(root){
// 当前节点为空，表示达到了叶子节点
if (root == null) return
// 接着找左子树
loop(root.left)
// 接着找右子树
loop(root.right)
}
loop(root)
对于前序遍历，中序遍历，后续遍历而言，分别在对应的位置访问节点的值即可，如下：
var preorder = []// 前序结果
var inorder = []// 中序结果
var postorder = []// 后序结果
var loop = function(root){
// 当前节点为空，表示达到了叶子节点
if (root == null) return
preorder.push(root.val) // 前序
loop(root.left)
inorder.push(root.val)// 中序
loop(root.right)
postorder.push(root.val)// 后序
}
loop(root)
递归的方法来遍历二叉树，其实是利用了深度优先搜索的思路，即从一个节点开始一直到他的左右节点，再次从左右节点再次深入，直到找到叶子节点或者根节点为止。
但是对于层序遍历来说，递归的思路就不是很适用了，思想是从上到下一层一层搜索，它更像是一种广度优先搜索的思路，即从一个节点开始所说它的所有左右节点，然后下一层每个节点的所有左右节点，利用这种思想，我们可以借助一个队列的数据结构来实现层序遍历。
队列是一种线性的数据结构，遵循先进先出的规则，在JavaScript中，由于没有队列这种数据结构，我们可以用数组Array来进行模拟，如下：
var queue = [] // 队列 (左边队头，右边队尾)
queue.push(1)// 入队1
queue.push(2)// 入队2
queue.push(3)// 入队3
//此时队列元素：[1,2,3]
queue.shift()// 出队1
queue.shift()// 出队2
层序遍历的思想就是：
-
根节点入队，然后遍历队列。 -
访问根节点，根节点出队，同时将根节点作为当前元素，分别将当前元素的左节点入队，右节点入队。（第一层结束）。 -
记录当前此时队列的元素个数，将上一步的左节点作为当前元素，访问当前元素的值，当前元素出队（元素个数减一），同时分别将当前元素的左节点入队，右节点入队。 -
依此重复上述操作，直到记录的元素个数为0时，表示此层结束。 -
每层都重复上述操作，直到整个队列为空时，则遍历结束。
转换成代码，如下：
var levelOrder1 = function(root) {
if (root == null) return []
var arr = []
arr.push(root) // 根节点入队
var res = []
while (arr.length) {
var len = arr.length
var floor = []// 存储每一层的数据
while (len) {
var temp = arr.shift()// 当前元素出队
if (!temp) break
// 每一层数据
floor.push(temp.val)
// 左节点入队
if (temp.left) {
arr.push(temp.left)
}
// 右节点入队
if (temp.right) {
arr.push(temp.right)
}
len--
}
// 存储每一层数据
res.push(floor)
}
return res
}
对于前序遍历，中序遍历，后续遍历而言，如果不使用递归，我们可以利用栈来获取遍历结果，栈是一种线性的数据结构，遵循先进后出的规则，在JavaScript中，由于没有栈这种数据结构，我们可以用数组Array来进行模拟，如下：
var stack = [] // 栈
stack.push(1)// 入栈1
stack.push(2)// 入栈2
stack.push(3)// 入栈3
//此时栈内元素：[1,2,3]
stack.pop()// 出栈3
stack.pop()// 出栈2
前序遍历：
-
根节点入栈，依此取出栈顶元素。 -
访问栈顶元素，同时出栈，将栈顶元素作为当前元素，当前元素右节点入栈，左节点入栈（注意：右先入那么右后出）。 -
重复上述操作，直到整个栈为空时，则遍历结束。
var preorderTraversal = function(root) {
var arr = []
arr.push(root)
var res = []
while (arr.length) {
var temp = arr.pop()
if (!temp) break
res.push(temp.val)
if (temp.right) {
arr.push(temp.right)
}
if (temp.left) {
arr.push(temp.left)
}
}
return res
};
中序遍历：
-
循环将根节点和其的左子树入栈。 -
直到左子树为空时，访问栈顶元素，同时将栈顶元素作为当前元素，并出栈。 -
开始访问右子树，循环出栈直到整个栈为空时，则遍历结束。
var inorderTraversal = function(root) {
var res = []
var arr = []
while(arr.length || root) {
if (root) {
arr.push(root)
root = root.left
} else {
var temp = arr.pop()
res.push(temp.val)
root = temp.right
}
}
return res
};
后序遍历：
和前序遍历思想相反。
var postorderTraversal = function(root) {
var arr = []
arr.push(root)
var res = []
while(arr.length) {
var temp = arr.pop()
if (!temp) break
res.unshift(temp.val)// 从前往后塞入数据
if(temp.left) {// 左节点先入栈
arr.push(temp.left)
}
if(temp.right) {
arr.push(temp.right)
}
}
return res
};
复杂度分析：
二叉树遍历的递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了递归，最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。
二叉树遍历的非递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了栈，空间复杂度为二叉树的高度，故空间复杂度为O(n)。
二叉树遍历时基本的二叉树操作，掌握好遍历技巧是进行后续二叉树相关操作的基础。