本文共 3877 字，大约阅读时间需要 12 分钟。

树的中序遍历（非递归） lc94

中序遍历：按照左，根，右的顺序遍历二叉树

思路——使用栈：先将根节点入栈，找到所有左节点入栈，直到没有左节点为止，然后出栈存入结果数组，每出一个，对比该根节点的右子节点是否有左节点，若有则入栈，否则继续出栈。

中序遍历，是一种深度搜索，探索根节点的左子树，左子树的左子树，左子树的左子树的左子树……直到左子树为空，这样一种特点需要用到栈的先进后出的特点。

具体操作是：对于任一节点p，

1. 若其左孩子不为空，则将p入栈并将p的左孩子置为当前的p，然后对当前结点p再进行相同的处理；
2. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将栈顶结点的右孩子置为当前的p
3. 直到p为null且栈为空则结束遍历

//中序非递归var inorder = function(root) {    if(!root)  //判断树是否为空        return [];    var p = root;    var stack = [], result = [];  //stack存放遍历过的根，左节点，以便回溯访问右节点    while(stack.length > 0 || p) {        //若其左孩子不为空，先将左子节点入栈        if(p != null) {   //if(p)            stack.push(p);            p = p.left        }else{  //若其左孩子为空，则取栈顶元素并进行出栈操作            p = stack.pop();            result.push(p.val);            p = p.right;        }    }    return result;};

树的先序遍历（非递归） lc144

先序遍历：按照根，左，右的顺序遍历二叉树

思路：建立一个栈，将根节点加入栈中，当栈不为空时：（栈的性质是 后进先出）

1、取出栈顶元素 curr，访问curr

2、若curr右子节点不为空，则将curr右子节点加入栈

3、若curr左子节点不为空，则将curr左子节点加入栈

//先序非递归 根左右var preorder = function (root) {    if (!root)  //判断树是否为空        return [];    var stack = [], result = [];  // result储存结果，stack存放遍历过的根，左节点，以便回溯访问右节点    stack.push(root);    while (stack.length !== 0) {        var curr = stack.pop();        if (curr.right)             stack.push(curr.right);        if (curr.left)             stack.push(curr.left);        result.push(curr.val);    }    return result;}

树的后序遍历（非递归） lc145

后序遍历：按照左，右，根的顺序遍历二叉树

• unshift()方法：可以在数组的前端添加一个或多个元素

var fruits = ["b", "c", "d", "e"];

fruits.unshift("1","2");  //输出[1, 2, b, c, d, e]

//后序非递归 左右根var postorder = function(root) {    if (!root)  //判断树是否为空        return [];    var result = [], stack = []; //result储存结果，stack存放遍历过的根，左节点，以便回溯访问右节点    stack.push(root)    while(stack.length !== 0){        result.unshift(root.val);  //从result数组头部插入根节点-右节点-左节点        if(root.left)            stack.push(root.left)        if(root.right)            stack.push(root.right)        root = stack.pop();  //先弹出右节点，再弹出左节点    }    return result;}

树的广度优先遍历(层序) BFS  NC15

思路：用队列实现

先将二叉树头结点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根结点入队；如果它有右子树，则将右子树的根结点入队。然后出队列，对出队结点访问，如此反复，直到队列为空为止。复杂度为O(n)。

如图所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3、4的层次顺序，对二叉树中各个结点进行访问。

• shift() 方法：把数组的第一个元素从其中删除，并返回第一个元素的值。

var fruits = ["Banana", "Orange", "Apple", "Mango"];

var shift = fruits.shift();

console.log(shift);  //Banana

console.log(fruits);  //[ 'Orange', 'Apple', 'Mango' ]

//广度优先遍历(层序)function levelOrder(root) {    if (!root)  //判断树是否为空        return [];    var res = [];  //存放结果    var queue = [root];  //辅助数组，用来取元素，长度为每层的元素个数    while (queue.length !== 0) {        var floor = []  //初始化一个空的子数组，存放的是每一层的节点值        var len = queue.length;        for (var i = 0; i < len; i++) {            var node = queue.shift();  //将头结点出队列            floor.push(node.val);            // 将该节点的左右孩子分别压入arr栈中，即下一层的节点            if (node.left) {                queue.push(node.left);            }            if (node.right) {                queue.push(node.right);            }        }        res.push(floor);  //最后的结果是一个二维数组    }    return res;}

深度优先与广度优先

• 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。
• 深度优先对每一个可能的分支路径深入到不能再深入为止,先序遍历、中序遍历、后序遍历属于深度优先。
• 广度优先又叫层次遍历，从上往下，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

二叉树前中后序递归遍历

前序：根左右

//前中后序递归遍历function threeOrders(root) {    const preRes = []    const inRes = []    const postRes = []    const preOrder = (node) => {  //前序：根左右        if (node === null) return        preRes.push(node.val)        preOrder(node.left)        preOrder(node.right)    }    const inOrder = (node) => {  //中序：左根右        if (node === null) return        inOrder(node.left)        inRes.push(node.val)        inOrder(node.right)    }    const postOrder = (node) => {  //后序：左右根        if (node === null) return        postOrder(node.left)        postOrder(node.right)        postRes.push(node.val)    }    preOrder(root)    inOrder(root)    postOrder(root)    return [preRes, inRes, postRes]}

转载地址：http://tnuvi.baihongyu.com/