|
算法依托于数据结构而存在，所以在每种语言中，或多或少，都会有一些专门针对这些数据结构来解决问题的方法。下面就谈一谈我的一些思考。
个人不才，总结了一个小小的公式，算法=数据结构+逻辑+(创新性)
在前端中，使用频率比较高的，应该就是数组，链表，队列，栈，二叉树以及Map和Set结构。
其中呢，由于数组的API很多很强大，在js中经常使用数组的pop和push来模拟栈操作。用数组的shift和push来模拟队列的操作，这很重要。Map和Set结构，可以对数组的某些方向增强(比如数组去重等等)?。思想上以迭代为主。
二叉树和链表呢，是乱序储存在堆中的，由于其都是通过指针来构成链式结构。所以在思想方法上以递归为主。当然，DFS和BFS的非递归调用也可以采用迭代的思想。
所以，在算法中呢，最基础的或许也是最有力量感的就是去体会一下迭代的神奇魅力了。
下面我就用二叉树的前序，中序，后序和层序的递归和非递归（迭代）来实现一下，对比两中基本的思想方法有何不同以及有何相同的。
首先先全局定义一个tree对象。
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
前序遍历，二叉树最基本的遍历。
//迭代法，利用数组模拟栈结构
var preorderTraversal = function(root) {
const result=[]
const stack=[]
if(root) stack.push(root)
while(stack.length){
const n=stack.pop()
result.push(n.val)
if(n.right)stack.push(n.right)
if(n.left)stack.push(n.left)
}
return result
}
//递归法
var preorderTraversal = (root) => {
let result = []
var preOrderTraverseNode = (node) => {
if(node) {
// 先根节点
result.push(node.val)
// 然后遍历左子树
preOrderTraverseNode(node.left)
// 再遍历右子树
preOrderTraverseNode(node.right)
}
}
preOrderTraverseNode(root)
?中序遍历。
//迭代法
var inorderTraversal = function(root) {
const stack = []
const res = []
let p = root
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
res.push(n.val)
p = n.right
}
return res
}
//递归法
var inorderTraversal = function(root) {
let result = [];
this.inOrder = function(root) {
if (root == null) {
return;
}
inOrder(root.left);
result.push(root.val);
inOrder(root.right);
}
inOrder(root);
return result;
}
后序遍历。
//非递归的栈思想
var postorderTraversal = function(root) {
if(!root)return []
let result=[]
let stack=[root]
while(stack.length){
let n=stack.pop()
//这一步数组操作很重要
result.unshift(n.val)
n.left && stack.push(n.left)
n.right && stack.push(n.right)
}
return result
}
//递归法
var postorderTraversal = function(root) {
const res = [];
if (!root) return res;
const postOrder = node => {
if (!node) return null;
postOrder(node.left);
postOrder(node.right);
res.push(node.val);
}
postOrder(root);
return res;
}
层序遍历。
//迭代法
var levelOrder = function(root) {
if(!root){
return []
}
let result=[]
let quene=[root]
while(quene.length!==0){
let queneLength=quene.length
let currentLevel=[]
for(let i=0;i<queneLength;i++){
let node=quene.shift()
currentLevel.push(node.val)
if(node.left)quene.push(node.left)
if(node.right)quene.push(node.right)
}
result.push(currentLevel)
}
return result
}
//递归法
var levelOrder = function (root, depth = 0, res = []) {
if (!root) {
return [];
}
res[depth] || (res[depth] = []);
res[depth].push(root.val);
levelOrder(root.left, depth + 1, res);
levelOrder(root.right, depth + 1, res);
return res;
}
可以看到，两大算法思想利器的力量！递归就是结构上简单，思想上复杂，迭代就是思想上简单，结构上复杂？会不会有二者兼得的呢？
以上就是表达我对于算法方面的部分思考。算法可以难得难道无解，知识体系，技巧“绝招”多种多样。如果有小伙伴也感兴趣的可以一起合作探讨啊！！如果有错误或者不当也请指正批评！！
|