基本概念
二叉树遍历次要为深度优先（DFS）和广度优先（BFS），其中深度优先遍历包含前序、中序、后序，广度优先遍历也叫层序遍历。
深度优先三种办法遍历程序：
其实很好记，就是两头节点在最后面、两头和最初面输入，而左右的绝对程序是固定的。
例如上面这棵树：
1 / \ 2 3 / \ / \4 5 6 7前序遍历：1, 2, 4, 5, 3, 6, 7
中序遍历：4, 2, 5, 1, 6, 3, 7
后序遍历：4, 5, 2, 6, 7, 3, 1
深度优先和广度优先都能通过递归实现，因为递归办法过于简略，面试考查的通常是非递归实现。深度优先的非递归办法通过堆栈实现，广度优先的非递归办法通过队列实现。
递归实现
前序遍历：
function preOrder(root) { if (root == null) return; console.log(root.val); // 输入管制 preOrder(root.left); preOrder(root.right);}而中序遍历和后序遍历则只需批改输入管制的地位。
中序遍历：
function inOrder(root) { if (root == null) return; inOrder(root.left); console.log(root.val); // 输入管制 inOrder(root.right);}后序遍历：
function postOrder(root) { if (root == null) return; postOrder(root.left); postOrder(root.right); console.log(root.val); // 输入管制}非递归实现
非递归版本应用堆栈实现，三种遍历办法次要是压栈弹栈的程序不同。
前序遍历：
一开始先把根节点压栈，每次弹出栈顶元素的同时输入该元素，而后把栈顶元素的右节点、左节点别离入栈（如果有的话，为空则不必）；直到栈为空则进行。
代码如下：
function preOrderByStack(root) { let res = new Array(); if (root == null) // 边界判断 return res; let stack = new Array(); stack.push(root); // 先把根节点压栈 while (stack.length > 0) { root = stack.pop(); // 弹出以后栈顶元素 res.push(root.val); // 保留后果 if (root.right != null) { stack.push(root.right); // 先压入右节点 } if (root.left != null) { stack.push(root.left); // 再压入左节点 } } return res;}下面的代码复用了root变量，益处就是不应用额定的变量，升高空间复杂度。
后序遍历：
后序遍历有一种十分trick的做法。咱们晓得先序遍历为中左右，而后序遍历为左右中，咱们把后序遍历反过来，就是中右左，是不是发现和先序遍历有点像了？咱们先序遍历采纳了先压入右节点再压入左节点的形式失去了中左右的程序，那么咱们只有先压入左节点，再压入右节点，就能失去中右左的程序，这里只有保留后果的时候从前往后插入，就变成了咱们想要的后序遍历了：左右中。
function preOrderByStack(root) { let res = new Array(); if (root == null) return res; let stack = new Array(); stack.push(root); while (stack.length > 0) { root = stack.pop(); res.unshift(root.val); // 从数组头部增加后果 if (root.left != null) { stack.push(root.left); // 先压入左节点 } if (root.right != null) { stack.push(root.right); // 再压入右节点 } } return res;}中序遍历：
以后节点只有有左节点，就将其左节点压栈，并且以后节点向其左节点方向挪动，直到以后节点为空，阐明此时位于最左下方的节点的空左节点处，那么接下来咱们就须要弹栈获取栈顶，输入元素，而后挪动到栈顶节点的右节点处。
代码如下：
function inOrderByStack(root) { let res = new Array(); let stack = new Array(); while (stack.length > 0 || (root != null)) { if (root != null) { // 以后节点非空，压栈后向左挪动 stack.push(root); root = root.left; } else { // 以后节点为空，弹栈输入后向右挪动 root = stack.pop(); res.push(root.val); root = root.right; } } return res;}层序遍历
简略来说就是一行一行地遍历，基于队列来做，先把根节点入队列，只有队列非空，每次把队头结点弹出，而后把堆头的左右节点压入队列中，这样最终遍历进去的就是层序遍历的程序。
function levelOrder(root) { if (root == null) return null; let res = new Array(); let queue = new Array(); queue.unshift(root); // 先把根节点入队列 while (queue.length > 0) { // 队列非空 root = queue.pop(); res.push(root.val); // 弹出队头节点 if (root.left != null) queue.unshift(root.left); if (root.right != null) queue.unshift(root.right); } return res;}参考：
二叉树遍历