二叉树的遍历是面试经常会考察的知识点，二叉树的遍历包括深度遍历和广度遍历，而广度遍历又分前序遍历、中序遍历和后序遍历。广度的遍历包含递归的实现方式和非递归的方式，本文整理了这些知识点，希望对大家有帮助。
深度遍历
深度遍历就是根据二叉树的层数一层一层遍历，实现深度遍历的关键是利用队列，当队列当中有元素的时候，取出队列的头部元素，访问这个元素，然后把这个元素的左孩子和右孩子入队列，然后重复这个过程。代码如下：
function bfs(node) {
var queue = []
queue.push(node)
// 队列一直有元素不断访问
while(queue.length) {
var item = queue.shift() // 取出队列的头部元素
console.log(item.value)
item.left && queue.push(item.left) // 入左孩子
item.right && queue.push(item.right) // 入右孩子
}
return result
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(bfs(node))
求二叉树的右视图
广度遍历的另外一个考点，就是求二叉树的右视图或者左视图，整体的思路就是遍历每一层的时候，把每一层的最后一个元素取出来。而如何判断每一层的最后一个元素是个关键。做法就是在遍历的时候，取出队列中的所有元素，这些元素就是每一层的所有元素(假设有n个)，然后循环这n个元素，判断下标是否为n-1，如果是，则是最后一个元素，同时每循环一次都需要取出左孩子和右孩子进队列，作为下一层遍历的元素。
function rightView(root) {
var result = []
var queue = []
queue.push(root)
while(queue.length) {
var len = queue.length
// 用for循环每一层
for (var i = 0; i < len; i++) {
var node = queue.shift()
// 判断是这一层的最后一个节点
if (i === len - 1) {
result.push(node.value)
}
// 将每层节点入队列
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
return result
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(rightView(node))
广度遍历
广度遍历一般比较容易的实现方式是递归的方式，但是对于非递归的方式我们也需要理解下，面试官更喜欢问非递归的方式。非递归的实现的方式，就是利用栈。
前序遍历
前序遍历的递归方式，就是先访问节点，再递归左树，最后递归右树。
递归方式：
function dfs(node) {
if (!node) return
console.log(node.value)
dfs(node.left)
dfs(node.right)
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))
非递归方式：
非递归实现前序遍历，主要是利用栈的先入后出特性，所以先入右树，再入左树。完整的过程描述如下：
1、先入根节点
2、当栈不为空，一直循环
3、取出栈顶元素，访问之
4、右孩子入栈
5、左孩子入栈
6、栈中有元素，一直循环2-5
function dfs(node) {
var stack = []
stack.push(node)
while (stack.length) {
var item = stack.pop()
console.log(item.value)
item.right && stack.push(item.right)
item.left && stack.push(item.left)
}
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))
中序遍历
递归方式
中序遍历的递归方式就是先递归左树，然后访问当前节点，再递归右树。
function dfs(node) {
if (!node) return
dfs(node.left)
console.log(node.value)
dfs(node.right)
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))
非递归方式
非递归的实现方式也是利用栈，先把左树入栈，然后取出栈顶元素，再把右树入栈。完整的过程描述如下：
1、当队列不为空或者当前节点不为空，一直循环
2、如果当前节点不为空，入栈，当前节点赋值为其左孩子
3、如果当前节点为空，则取出栈顶元素，访问之，并把当前节点赋值为其右孩子
4、不断循环1-3直到栈为空且当前节点不存在
function dfs(node) {
var stack = []
while (stack.length || node) {
if(node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
console.log(node.value)
node = node.right
}
}
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))
后序遍历
递归方式
后序遍历的递归方式就是先访问左树，再访问右树，最后访问当前节点。
function dfs(node) {
if (!node) return
dfs(node.left)
dfs(node.right)
console.log(node.value)
}
// 例子
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))
非递归方式
非递归的实现方式同样是利用栈，先把根结点和左树推入栈，然后取出左树，再推入右树，取出，最后取根结点。特殊的情况是，遍历的同时需要做个标记，防止重复入栈，完整的过程描述如下：
1、当队列不为空一直循环
2、如果当前节点有左孩子且左孩子未touch过，则其左孩子入栈，并标记当前节点的左孩子touch过，然后把当前节点指向其左孩子，一直循环到没有左孩子
3、如果当前节点有右孩子且右孩子未touch过，则其右孩子入栈，并标记当前节点的右孩子touch过，然后把当前节点指向其右孩子，一直循环到没有右孩子
4、取出栈顶元素，访问之，把当前节点指向栈中最后一个元素
5、循环2-5直到栈为空
function dfs(node) {
var stack = []
stack.push(node)
while(stack.length) {
// 这里不能用node.touched === 'left'，因为这个时候被右树访问过会是right，如果用left会再执行，死循环
if (node.left && !node.touched) {
node.touched = 'left'
node = node.left
stack.push(node)
continue
}
if(node.right && node.touched !== 'right') {
node.touched = 'right'
node = node.right
stack.push(node)
continue
}
node = stack.pop() // 该节点无左右树时，取出访问
console.log(node.value)
// 这时当前结点不再从栈中取（弹出），而是不改变栈数据直接访问栈中最后一个结点，不然后序访问就没有了
node = stack.length ? stack[stack.length - 1] : null;
}
}
var node = {value: 0, left: {value: 1, left: {value: 3}, right: {value: 4}}, right: {value: 2}}
console.log(dfs(node))