二叉树递归及非递归遍历
原始数据：
var root = {
val:1,
left:{
val:2,
left:{
val:4,
},
right:{
val:5,
}
},
right:{
val:3,
left:{
val:6,
},
right:{
val:7,
}
}
}
递归遍历 - 先序遍历
function DLR(root) {
if(root!=null) {
console.log(root.val);
DLR(root.left);
DLR(root.right);
}
}
DLR(root); // 1,2,4,5,3,6,7
递归遍历 - 中序遍历
function LDR(root) {
if(root!=null) {
LDR(root.left);
console.log(root.val);
LDR(root.right);
}
}
LDR(root); // 4,2,5,1,6,3,7
递归遍历 - 后序遍历
function LRD(root) {
if(root!=null) {
LRD(root.left);
LRD(root.right);
console.log(root.val);
}
}
LRD(root); // 4,5,2,6,7,3,1
非递归遍历 - 前序遍历
function DLR(root) {
var arr=[],res=[];
if(root!=null) {
arr.push(root);
}
while(arr.length!=0) {
var temp = arr.pop();
res.push(temp.val);
if(temp.right!=null) {
arr.push(temp.right);
}
if(temp.left!=null) {
arr.push(temp.left);
}
}
return res;
}
DLR(root); // 1,2,4,5,3,6,7
非递归遍历 - 中序遍历
function LDR(root) {
var arr=[],res=[];
while(true) {
while(root!=null) {
arr.push(root);
root=root.left;
}
//终止条件
if(arr.length==0) {
break;
}
var temp = arr.pop();
res.push(temp.val);
root=temp.right;
}
return res;
}
LDR(root); // 4,2,5,1,6,3,7
非递归遍历 - 后序遍历
function LRD(root) {
var arr=[],res=[];
arr.push(root);
while(arr.length!=0) {
var p = arr.pop();
res.push(p.val);
if(p.left!=null) {
arr.push(p.left);
}
if(p.right!=null) {
arr.push(p.right);
}
}
return res.reverse();
}
LRD(root); // 4,5,2,6,7,3,1
归并排序merge sort O(nlgn)
- 分：将数据集等分为2半
- 治：分别在2个部分用递归的方式继续使用归并排序法
合：将分开的2个部分合并成一个有序的数据集
Merge sort A[1…N]
If n=1 done
Recursively sort A[1…[n/2]向上取整] and A[[n/2]向上取整+1…n]
Merge 2 sorted lists
辗转相除法（求最大公约数和最小公倍数）
计算两个非负整数 p 和 q 的最大公约数:若 q 是 0，则最大公约数为 p。否则，将 p 除以 q得到余数r，p和q的最大公约数即为q和 r 的最大公约数。
while（b不为0）
{
temp=a%b；
a=b；
b=temp
}
最后a即为两数的最大公约数，最大公倍数为： a*b/最大公约数
KMP算法
Knuth-Morris-Pratt 字符串查找算法，简称为KMP算法，常用于在一个文本串S内查找一个模式串P的出现位置
甲：abbaabbaaba
乙：abbaaba
目标：发生不匹配，自身不回退。
发现：当在甲的某个字符 c 上发生不匹配时，甲即使回退，最终还是会重新匹配到字符 c 上。
甲不回退，乙必须回退地尽可能少，并且乙回退位置的前面那段已经和甲匹配，这样甲才能不用回退。
如何找到乙回退的位置？
「不匹配发生时，前面匹配的那一小段 abbaab 于我俩是相同的」，甲想，「这样的话，用 abbaab 的头部去匹配 abbaab 的尾部，最长的那段就是答案。」
abbaab 的头部有 a, ab, abb, abba, abbaa（不包含最后一个字符。称之为「真前缀」）
abbaab 的尾部有 b, ab, aab, baab, bbaab（不包含第一个字符。称之为「真后缀」）
这样最长匹配是 ab。也就是说甲不回退时，乙需要回退到第三个字符去和甲继续匹配。
「要计算的内容只和乙有关」，甲想，「那就假设乙在其所有位置上都发生了不匹配，乙在和我匹配前把其所有位置的最长匹配都算出来（算个长度就行），生成一张表，之后我俩发生不匹配时直接查这张表就行。」
据此，甲总结出了一条规则并告诉了乙：
所有要与甲匹配的字符串（称之为模式串），必须先自身匹配：对每个子字符串 [0…i]，算出其「相匹配的真前缀与真后缀中，最长的字符串的长度」。
例如：abababzabababa
列个表手算一下：（最大匹配数为子字符串 [0...i] 的最长匹配的长度）
子字符串 a b a b a b z a b a b a b a
最大匹配数 0 0 1 2 3 4 0 1 2 3 4 5 6 5
容易看出次大匹配了 4 个（abab），更仔细地观察可以发现，次大匹配必定在最大匹配 ababab 中，所以次大匹配数就是 ababab 的最大匹配数！
