二叉树的遍历方式主要有：先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中，父节点先于它的子节点被访问，就是先序遍历；父节点被访问的次序位于左右孩子节点之间，就是中序遍历；访问完左右孩子节点之后再访问父节点，就是后序遍历。不论是先序遍历、中序遍历还是后序遍历，左右孩子节点的相对访问次序是不变的，总是先访问左孩子节点，再访问右孩子节点。而层次遍历，就是按照从上到下、从左向右的顺序访问二叉树的每个节点。
1、递归遍历（前、中、后）
//节点结构
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
//1、前序遍历
function DLR(root){
console.log(root.val);
if(root.left){
DLR(root.left);
}
if(root.right){
DLR(root.right);
}
}
//2、中序遍历
function LDR(root){
if(root.left){
LDR(root.left);
}
console.log(root.val);
if(root.right){
LDR(root.right);
}
}
//3、后序遍历
function LRD(root){
if(root.left){
LRD(root.left);
}
if(root.right){
LRD(root.right);
}
console.log(root.val);
}
2、层序遍历
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function levelTraversal(root){
if ( !root ) return false;//如果头结点为空、返回假
var result = []; //创建一个数组存放结果
var tree = []; //创建一个数组存放二叉树
tree.push(root); //先传入头结点
// 当tree数组长度不为空
while( tree.length ){
var node = tree.shift(); // 将数组第一个结点放到node中
result.push(node.val); //将node结点的值压入result数组中
//如果node结点左子树不为空
if( node.left ){
tree.push(node.left); // 将node结点的左子树结点的值压入tree数组中
}
//如果node结点又子树不为空
if( node.right ) {
tree.push(node.right); //将node结点的右子树结点的值压入tree数组中
}
}
return result; //返回result数组
}
3、重建二叉树
根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。
function reConstructBinaryTree(pre, vin)
{
var res = null;
if(pre.length===1){
res = {
val: pre[0],
left: null,
right: null,
}
}else if(pre.length >1){
var root = pre[0];
var rootIndex = vin.indexOf(root); //记录根节点在中序遍历中的位置
var vinLeft = vin.slice(0,rootIndex); //分割中序遍历得到左子树
var vinRight = vin.slice(rootIndex+1,vin.length); //分割中序遍历得到右子树
pre.shift(); //去掉pre第一个元素并返回该元素。
var preLeft = pre.slice(0,vinLeft.length);
var preRight = pre.slice(vinLeft.length,pre.length);
res = {
val: root,
left: reConstructBinaryTree(preLeft,vinLeft),
right: reConstructBinaryTree(preRight,vinRight),
}
}
return res;
}
