共计 5951 个字符，预计需要花费 15 分钟才能阅读完成。
- 二叉树广度遍历
- 二叉树层序遍历
- 二叉树深度遍历：前序，中序，后序
- 二叉树的最大深度
- 二分查找
- 给定 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));疾速排序
分两个过程：
- 划分：依据 partition 函数把数组从基准位划分为 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 数据结构与算法
正文完
发表至： javascript
2021-03-08
