• 二叉树广度遍历
  • 二叉树层序遍历
  • 二叉树深度遍历：前序，中序，后序
  • 二叉树的最大深度
  • 二分查找
  • 给定path，遍历树查找有无指定path的节点
  • 疾速排序
  • 第K大
  • 最长公共前缀
  • 无反复字符的最长子串

树遍历很多先定义一个树型构造。

// 树形构造定义const tree = {      data: 1,      left: {        data: 2,        left: {          data: 4,          left: {            data: 8,          },          right: {            data: 9          }        },        right: {          data: 5,          left: {            data: 10,          },          right: {            data: 11          }        }      },      right: {        data: 3,        left: {          data: 6,          left: {            data: 12          }        },        right: {          data: 7        }      }    };

二叉树广度遍历

广度遍历就是遍历每一层，下面的tree 广度遍历之后的后果是[1,2,3,4,5,6,7,8,9,10,11,12]。实现形式是通过栈保留遍历状态，按父节点，左子树，右子树的程序压栈。取出栈顶保留到后果数组中，等栈为空时遍历完结。

代码如下：

// 广度遍历function bfs(tree){    // 通过栈保留遍历状态    let stack = [tree];    let result = [];        while(stack.length){        // 取出栈顶        const node = stack.shift();                result.push(node.data);        // 有左子树压到栈中        if(node.left){            stack.push(node.left);        }        // 右右子树压到栈中        if(node.right){            stack.push(node.right);        }    }    return result;}console.log('广度遍历', bfs(tree));

二叉树层序遍历

层序遍历是每个档次保留到一个数组项。

    // 层序遍历        function levelOrder(tree){            const output = [];            let level = 0;            if(level === null){                return output;            }            const visitLoop = (node, level) => {                if(!output[level]){                    output[level] = [];                }                output[level].push(node.data);                if(node.left){                    visitLoop(node.left, level + 1);                }                if(node.right){                    visitLoop(node.right, level + 1);                }            };            visitLoop(tree, 0);            return output;        }        console.log('层序遍历', levelOrder(tree));

二叉树前序遍历

前序遍历的程序是先拜访根，再拜访左子树，再拜访右子树。前序遍历的后果是[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7]。
利用栈的个性保留以后遍历状态。初始化根节点先压栈。每次循环中取出栈顶保留到后果数组中，如果有右子树压栈，有左子树压栈。

// 前序遍历function preOrder(tree){    let stack = [tree];    let result = [];    let node;    while(stack.length){        let node = stack.pop();        result.push(node.data);        if(node.right){            stack.push(node.right);        }        if(node.left){            stack.push(node.left);        }    }    return result;}console.log('前序遍历', preOrder(tree));

前序遍历的递归实现

// 前序遍历递归实现function preOrderRcs(tree){    let result = [];    const visitLoop = function(node){        result.push(node.data);        if(node.left){            result.concat(visitLoop(node.left));        }        if(node.right){            result.concat(visitLoop(node.right));        }    };    visitLoop(tree);    return result;}console.log('前序遍历-递归实现', preOrderRcs(tree));

二叉树中序遍历

中序遍历是先拜访左子树，在拜访根，最初拜访右子树。中序遍历后果为[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7]。
中序遍历非递归实现用到了回溯算法。

回溯法（back tracking）（摸索与回溯法）是一种选优搜寻法，又称为试探法，按选优条件向前搜寻，以达到目标。但当摸索到某一步时，发现原先抉择并不优或达不到指标，就退回一步从新抉择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

非递归遍历还是利用栈保留遍历程序，加一个变量存储以后遍历节点。
遍历条件：栈不为空或者以后节点不为空
有以后节点存入栈中，顺次让左子树入栈，不存在左子树时，从栈顶弹出元素存入后果数组，如果弹出元素有右子树，右子树为以后遍历节点，压栈。

// 中序遍历 须要用到回溯算法        function inOrder(tree){            const stack = [];            const result = [];            // 以后遍历节点存储            let node = tree;                        while(stack.length || node){                // 有节点就压栈，并往下找左子树                if(node){                    stack.push(node);                    node = node.left;                }else{                    // 没有左子树了，从栈顶弹出                    const current = stack.pop();                    // 存到后果数组中                    result.push(current.data);                                        // 有右子树，以后遍历节点为右子树                    if(current.right){                        node = current.right;                    }                }            }            return result;        }        console.log('中序遍历', inOrder(tree));
// 递归实现function inOrderRcs(tree){    let result = [];        const visitLoop = function(node){        if(node.left){            result.concat(visitLoop(node.left));        }        result.push(node.data);        if(node.right){            result.concat(visitLoop(node.right));        }    };    visitLoop(tree);    return result;}console.log('中序遍历-递归实现', inOrderRcs(tree));

二叉树后序遍历

先遍历左子树，再遍历右子树，最初拜访根。后序遍历后果为 [8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1]。

除了保留遍历程序的栈和存储以后遍历节点之外，每个节点加上touched属性。以后节点有左子树时顺次遍历压栈，以后节点touched设为left。以后节点有右子树时顺次遍历压栈，以后touched设为false。如果遍历到叶子节点或者左右子树都已遍历过，存到后果数组。并把以后遍历节点设为栈顶元素。

// 后序遍历function postOrder(tree){    const stack = [tree];    const result = [];    let node = tree;    while(stack.length){        // 顺次把左子树压栈，以后节点标记为拜访过左子树        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;        }        // 如果是叶子结点或者左右子节点被拜访过        const current = stack.pop();        result.push(current.data);                // 设置栈顶为下一个拜访的元素        node = stack[stack.length - 1];    }    return result;}console.log('后序遍历', postOrder(tree))
// 后续遍历-递归function postOrderRcs(tree){    let result = [];    const visitLoop = function(node){        if(node.left){            result.concat(visitLoop(node.left));        }        if(node.right){            result.concat(visitLoop(node.right));        }        result.push(node.data);    };    visitLoop(tree);    return result;}console.log('后序遍历-递归实现', postOrderRcs(tree))

二叉树的最大深度

// 二叉树的最大深度function maxDepth(tree){    if(tree === null){        return 0;    }    let res = 0;    const visitLoop = (node, level) => {        if(!node){            return 0;        }        if(!node.left && !node.right){            res = Math.max(res, level);        }        if(node.left){            visitLoop(node.left, level + 1);        }        if(node.right){            visitLoop(node.right, level + 1);        }    };    visitLoop(tree, 1);    return res;}console.log('二叉树的最大深度', maxDepth(depthTree));

二分查找

function binarySearch(nums, target){    if(!nums.length){        return -1;    }    let start = 0        let end = nums.length - 1;        let mid;        while(start <= end){            let mid = Math.floor((start + end) /2);            if(target === nums[mid]){                return mid;            }            if(target < nums[mid]){                end = mid - 1;            }            if(target > nums[mid]){                start = mid + 1;            }        }        return -1;}console.log('二分查找', binarySearch([-1,0,3,5,9,12], 9));

疾速排序

分两个过程：

  1. 划分：依据partition函数把数组从基准位划分为2局部，基准位之前的比它小，之后的比它大。排序时采纳左右两个指针，遍历之后如果碰到右边比基准值大左边的小的值时替换两个值，并返回右边的指针。
  2. 递归：有个主函数quickSortHandler，通过执行partition取到左指针坐标，依据该坐标拆分数组进行递归。终止条件是数组长度。
// 疾速排序function quickSort(nums = []){    const swap = (nums, i ,j) => {        const temp = nums[j];        nums[j] = nums[i];        nums[i] = temp;    };    //划分过程    const partition = (nums, i, j) => {        let left = i;        let right = j;        let mid = Math.floor((right + left)/2);        // 左指针比右指针大时        while(left <= right){                        while(nums[left] < nums[mid]){                left++;            }            while(nums[right] > nums[mid]){                right --;            }            if(left <= right){                swap(nums, left, right);                left++;                right --;            }        }        return left;    };    // 拆分数组递归调用排序    const quickSortHandler = (nums, left, right) => {        let index;        // 终止条件        if(nums.length > 1){            index = partition(nums, left, right);            if(left < index - 1){                quickSortHandler(nums, left, index - 1);            }            if(index < right){                quickSortHandler(nums, index, right);            }        }        return nums;    };    quickSortHandler(nums, 0, nums.length - 1);    return nums;}console.log('疾速排序', quickSort([5,1,1,2,0,0]));

第K大

疾速排序之后找出数组中arr.length - k 的元素即可。

最长公共前缀

//最长公共前缀function longestCommonPrefix(strs = []){    if(!strs.length){        return '';    }    let res = strs[0];    for(let i = 1; i < strs.length; i++){        let j = 0;        for(;j < strs[i].length; j++){            if(strs[i][j] !== res[j]){                break;            }        }        res = res.substring(0, j);        if(!res){            return '';        }    }    return res;    }console.log('最长公共前缀', longestCommonPrefix(["flower","flow","flight"]));

无反复字符的最长子串

// 无反复字符的最长子串function lengthOfLongestSubstring(s){    let max = 0;    const arr = [];    if(!s){        return '';    }    for(let i = 0; i< s.length; i++){        if(arr.find(item => item ===s[i])){            let index = arr.findIndex(item => item === s[i]);            arr.splice(0, index + 1);        }        arr.push(s[i]);        max = Math.max(arr.length, max);    }    return max;}console.log('无反复字符的最长子串', lengthOfLongestSubstring('abcabcbb'));

参考文章：
二叉树遍历
学习javascript数据结构与算法