稳定的排序方法：冒泡、插入、归并、基数、二叉树排序（插、冒、二、归、基）
不稳定的排序方法：选择、希尔、堆、快速排序（快、选、堆、希）
每次排序后至少能确定一个元素的位置的排序有：
选择、冒泡、快排、堆排（堆顶元素确定）
每次排序后不能确定的有：插入、shell、归并、基数、计数
元素的移动次数与关键字的初始排列次序无关的是：基数排序
元素的比较次数与初始序列无关是：选择排序
算法的时间复杂度与初始序列无关的是：堆排序
其中最好、最坏、平均三项复杂度全是一样的就是与初始排序无关的排序方法：选择排序、堆排、归并、基数
时间复杂度为O（n2） 其中最好的时间复杂度为O（n）,最差的时间复杂度为O（n2）；空间复杂度O(1);属于稳定排序；初始数据基本有序，可用。第一次排序后，最大的数到达数组的末尾。主要理解冒泡的含义，相邻的两个不断的进行比较，冒泡排序最简单，效率最低
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
时间复杂度为O（n2），空间复杂度O(1)，比较次数与关键字的初始状态无关，属于不稳定排序；第一次排序后，最小数在首位（或者最大的数放末尾），主要理解选择的含义，每次选择剩余元素中最小值放在前面。选择排序是改进了冒泡排序，减少了移动的次数
int temp;
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// change
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
复杂度为O（n2），空间复杂度O(1)，属于稳定排序；每次对新插入数之前的数进行排序，主要理解插入的含义，他的思想是假设第一数是有序的序列（局部有序），然后依次将第二、第三个数与这个有序队列里面的数进行比较，在合适的地方插入，这是三种基本排序中效率最高的排序，一般情况下，比冒泡排序快一倍
int tar, j;
for (int i = 1; i < arr.length; i++) {
j = i;
tar = arr[i];
// 注：必须先 j>0，否则在j=0判断时，j-1可能出现数组越界异常
while (j > 0 && arr[j - 1] >= tar) {
arr[j] = arr[--j];
}
arr[j] = tar;
}
时间复杂度O(n(log2n))，其中最好的O(n(logn))，最差的为O(n2)；空间复杂度O(1)；基于插入排序，属于不稳定排序；他的思想是分组节点排序排序，然后不断的缩短间隔再次排序，直到间隔为1；这里不取1/2，据研究，当增量为质数的时候，希尔排序的效率会得到提高，这我们就可以放弃h=h/2的增量选择，选用h=h*3+1的做法。【注意】增量指的从第i个元素到第i+h个元素，指的是下标（从0开始）包头包尾
// 最终增量
int h = 1;
// 反推初始增量
while (h < arr.length / 3) {
h = h * 3 + 1;
}
int j, tar;
while (h > 0) {
// 插入排序
for (int i = h; i < arr.length; i++) {
j = i;
tar = arr[i];
while (j > h - 1 && arr[j - h] > tar) {
arr[j] = arr[j - h];
j = j - h;
}
arr[j] = tar;
}
// 缩减增量
h = (h - 1) / 3;
}
时间复杂度为O(nlogn)，空间复杂度O(n);与初始状态无关，外部排序常用的算法，归并的趟数为O(logn)要优于前三者的排序方式，他的思想是将已有序的子序列合并，得到完全有序的序列；缺点：归并排序需要存储器中有一个长度等于被排序数组的长度的额外数组，如果待排序数组占据了大部分的储存空间，归并排序将不能正常工作。她的思想：什么都不管，递归分两组，直到数组中只有一个元素，然后再排序，实质上就是对两个有序的子序列进行排序。以上说的二路归并的情况，多路归并的时候注意公式：m个元素k路归并的归并趟数s=logk(m)
//归并中的递归
public static void preMerge(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {//即处理的数组不为空
// 左边
preMerge(arr, low, mid);
// 右边
preMerge(arr, mid + 1, high);
// 左右归并
mergeSort(arr, low, mid, high);
}
}
//归并排序
public static void mergeSort(int[] arr,int low,int mid,int high) {
int[] temp = new int[high-low+1];//归并的特性，在内存中需要一个长度一样的数组来存放处理结果，也是体现它缺点的地方
int i = low;//左指针
int j = mid + 1;//右指针
int k =0;
while(i<=mid&&j<=high) {//这里已经将数组分成左右两个部分了
if(arr[i]<arr[j]) {//左边数组小放进去
temp[k++] = arr[i++];
} else {//右边数组的数据小放进去
temp[k++] = arr[j++];
}
}
while(i<=mid) {//左边部分的数组还有数据
temp[k++] = arr[i++];
}
while(j<=high) {//右半部份的数组还有数据
temp[k++] = arr[j++];
}
for(int m=0;m<temp.length;m++) {
arr[m+low] = temp[m];
}
}
时间复杂度为O（NlogN），最快的；
空间复杂度：最优为O（logN）,最差为O（N），
属于不稳定排序。
这里注意的当初始数组基本无序的时候，快速排序效率是比高的，初始的数组基本有序的话，这时的快速排序会非常不幸的退化为冒泡排序方，此时效将会非常低下；快速排序首先需要选一个枢纽（通常取数组的第一个数据），然后将所有比他小的放到他的前面，比他大的放到他的后面。他的思想是通过把数组划分为两个子数组，然后递归调用自身。为每个子数组进行快速排序来实现。具体的实现过程如下（这里顺序不能乱，是先从后往前，再从前往后）：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j；
技巧总结先从后往前寻找第一个小于枢纽值的数，然后再从前往后寻找第一个大于枢纽值的数，将这两者将换位置，最后进调整，将枢纽值和刚刚调到前面的数据进行一次位置交换，直到前后的指针遇到一起算是一趟
public static void quickSort(int array[], int start, int end) {
// i相当于助手1的位置，j相当于助手2的位置
int i = start, j = end;
int pivot = array[i]; // 取第1个元素为基准元素
int emptyIndex = i; // 表示空位的位置索引，默认为被取出的基准元素的位置
// 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
while (i < j) {
// 助手2开始从右向左一个个地查找小于基准元素的元素
while (i < j && pivot <= array[j]) {
j--;
}
if (i < j) {
// 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
array[emptyIndex] = array[j];
emptyIndex = j;
}
// 助手1开始从左向右一个个地查找大于基准元素的元素
while (i < j && array[i] <= pivot) {
i++;
}
if (i < j) {
// 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
array[emptyIndex] = array[i];
emptyIndex = i;
}
}
// 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
array[emptyIndex] = pivot;
// =====本轮快速排序完成=====
// 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
if (i - start > 1) {
quickSort(array, 0, i - 1);
}
// 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
if (end - j > 1) {
quickSort(array, j + 1, end);
}
}
时间复杂度为O（NlogN）（最好、最差、平均都是这个），其中构建堆的时间为N,和快速排序一样，但他没有快速排序快,空间复杂度为O（1）;属于不稳定排序;初始化数组集的排序顺序对算法的性能无影响，他的思想是：先构建堆(这里是指大顶堆，即根节点的值大于等于左右子节点的值)，再选择顶，并与第0个位置元素交换，这一步可能破坏最大堆（即最大元素不再是第0个元素），此时需要重新调整，这也是堆排序为什么不稳定的原因.
注：这里关于二叉树的常识要了解一下，堆是一颗完全二叉树，底层如果用数组存储的话，对于下标为n（从0开始）的节点而言，那她的左子树下标为2n+1,右子树下标2n+2,父节点为（n-1）/2,（如果父节点和子节点存在的话）
public static void heapSort(int[] arr) {
//构建大顶堆
for(int i=arr.length/2;i>=0;i--) {
heapAdjust(arr,i,arr.length);
}
//逐步将每个最大值的根节点与末为节点元素交换，并且调整二叉树，使其成为大顶堆
for(int i=arr.length-1;i>0;i--) {
swap(arr,0,i);
heapAdjust(arr,0,i);
}
}
public static void heapAdjust(int[] arr,int i,int n) {
int child;
int father;
for(father=arr[i];leftChild(i)<n;i=child) {
child = leftChild(i);
//如果左子树小于右子树，则需要比较右子树和父节点
if(child!=n-1&&arr[child]<arr[child+1]) {
child++;//序号增加1，指向右子树
}
//如果父节点小于孩子节点，则需要交换
if(father<arr[child]) {
arr[i] = arr[child];
} else {
break;//大顶堆结构未被破坏，不需要调整
}
}
arr[i] = father;
}
//获取到左孩子节点
public static int leftChild(int i) {
return 2*i+1;
}
//交换元素位置
public static void swap(int[] arr,int index1,int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
属于稳定排序；空间复杂度为O（n）;基数排序不需要比较操作，这里以10为基为例说一下他的操作流程是：
第一趟–排序根据个位上的值，将所有的数据分为10组，将所有以0为结尾的数据排在最前面，然后是是1为结尾的数据，依次排序，最后是以9为结尾的数据;
第二趟–将数据分为10组，但这一次的分组是根据十位上的数进行分组，这一次的分组不能改变上一次以个位分组的相对顺序；
。
。
。
最后–合数据，排在最前面的是十位上为0的数据，然后是十位上是1的数据，依次排序
二分查找法
时间复杂度为O(logn)
int foo(int array[], int n, int key) {
int n1 = 0, n2 = n - 1, m;
while (n1 <= n2) {
m = (n1 + n2) / 2;
if (array[m] == key)
return m;
if (array[m] > key)
n2 = m - 1;
else
n1 = m + 1;
}
return -1;
}
package com.hhu.sort;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/*
* 二叉树的常见题型
*/
public class BinaryTreeDemo {
//定义二叉树
private static class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
}
}
/*
* 1.求二叉树的节点数,迭代法，利用队列来遍历二叉树，从上到下，同一层从左到右
*/
public static int getNodeNumber(TreeNode root) {
TreeNode cur = root;
//这里务必不能随便省去，否则出问题
if(root==null) {
return 0;
}
int count = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
/*将根节点放入队列并且返回true,若果队列已满，则返回false
* 这里注意一下offer和add方法两者的区别，add方法功能一样
* 但是如果队列已满再往队列中add的话将会抛出unchecked异常
*/
queue.offer(cur);
while(!queue.isEmpty()) {//判断队列是否为空
//根节点不为空，节点数加一
count++;
/*将队列中第一个元素删除并且返回该元素，如果队列为空则返回null,
* 同样的，还有remove方法，功能一样，但是若队列为空那么将会抛出
* 异常
*/
cur = queue.poll();
if(cur.left!=null) {
//直接把做左子树丢进去
queue.offer(cur.left);
}
if(cur.right!=null) {
//再把右子树丢进去
queue.offer(cur.right);
}
}
return count;
}
/*
* 1.2利用递归的方法来实现节点数目的查找
*/
public static int getNodeNumber2(TreeNode root) {
TreeNode cur = root;
if(cur==null) {
return 0;
} else {
return getNodeNumber2(cur.left) + getNodeNumber2(cur.right) + 1;
}
}
/*
* 2.求二叉树的高度,迭代法
*/
public static int getHight(TreeNode root) {
TreeNode cur = root;
if(cur==null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//将根节点放到队列中
queue.offer(cur);
int ccount = 1;//当前层的节点数目
int ncount = 0;//下一层的节点数目
int depth = 0;//深度
while(!queue.isEmpty()) {
//删除队列中的一个元素
cur = queue.poll();
ccount--;
if(cur.left!=null) {
ncount++;//下一层节点数加一
queue.offer(cur.left);//将左子树放进队列
}
if(cur.right!=null) {
ncount++;//下一层节点加一
queue.offer(cur.right);//将右子树放进队列
}
if(ccount==0) {//如果当前层节点数为0，即便遍历完当前层的所有节点
depth++;//该层遍历完了深度才进行加1
ccount = ncount;//把即将遍历的下一层节点数赋给当前层节点数
ncount = 0;//下一层节点数置0
}
}
return depth;
}
/*
* 2.2利用递归的方法求数的高度,
* 如果二叉树为空，这深度为0
* 如果二叉树不为空，深度=max(左子树深度，右子树深度) + 1
*/
public static int getHight2(TreeNode root) {
TreeNode cur = root;
if(cur==null) {
return 0;
}
int leftHight = getHight2(cur.left);
int rightHight = getHight2(cur.right);
//自带的取最大值的方法
return Math.max(leftHight, rightHight)+1;
}
/*
* 3.遍历二叉树（迭代法）：前序、中序、后续
*/
//前序遍历，用Stack或者Queue做辅助
public static void preOrder(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(cur);
//思路：首先打印根节点，然后将右、左节点分别压栈（栈是先进后出，所以先压右节点，再压左节点）
while(!stack.isEmpty()) {
cur = stack.pop();
System.out.print(cur.val + " ");
if(cur.right!=null) {
stack.push(cur.right);
}
if(cur.left!=null) {
stack.push(cur.left);
}
}
}
//中序遍历,先将根节点的所有左孩子添加到栈，然后输出栈顶元素，再处理右孩子
public static void midOrder(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(true) {
while(cur!=null) {
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()) {
break;
}
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
}
//后序遍历，利用stack实现
public static void posOrder(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
//这个栈用来存放当前节点和它的做右节点
Stack<TreeNode> stack = new Stack<TreeNode>();
//这个栈用来反转前者栈的存放顺序
Stack<TreeNode> output = new Stack<TreeNode>();
//一开始先将根节点放到一个栈中
stack.push(cur);
while(!stack.isEmpty()) {
//如果栈不为空，者进行弹栈操作
cur = stack.pop();
//将弹栈的元素存入另一个栈中
output.push(cur);
if(cur.left!=null) {
stack.push(cur.left);
}
if(cur.right!=null) {
stack.push(cur.right);
}
}
while(!output.isEmpty()) {
System.out.print(output.pop().val + " ");
}
}
/*
* 3.2利用递归方法遍历二叉树
*/
//前序遍历
public static void preOrder2(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
System.out.print(cur.val + " ");
preOrder(cur.left);
preOrder(cur.right);
}
//中序遍历
public static void midOrder2(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
midOrder(cur.left);
System.out.print(cur.val + " ");
midOrder(cur.right);
}
//后续遍历
public static void posOrder2(TreeNode root) {
TreeNode cur = root;
if(cur==null) return;
posOrder2(cur.left);
posOrder2(cur.right);
System.out.print(cur.val + " ");
}
/*
* 4.分层(迭代法)遍历二叉树,从上到下，同一层从左到右
*/
public static void printBinary(TreeNode root) {
TreeNode cur =root;
if(cur==null) return ;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(cur);
while(!queue.isEmpty()) {
cur = queue.poll();
System.out.print(cur.val + " ");
if(cur.left!=null) {
queue.offer(cur.left);
}
if(cur.right!=null) {
queue.offer(cur.right);
}
}
}
/*
* 4.1利用递归实现分成打印
*/
public static void printBinary2(TreeNode root) {
//每一层元素单独存放到一个List中，然后将这些List统一存放到一个最终的List中
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
//
dfs(root, 0, ret);
System.out.println(ret);
}
public static void dfs(TreeNode root,int level, ArrayList<ArrayList<Integer>> ret) {
if(root==null) return;
//如果当前层数大于等于总的List记录数，则在大的List中添加一个空的List做存放容器
if(level>=ret.size()) {
ret.add(new ArrayList<Integer>());
}
//往最后的索引位置添加记录
ret.get(level).add(root.val);
dfs(root.left, level+1, ret);
dfs(root.right, level+1, ret);
}
/*
* 5.将二叉树变为有序的双向链表,要求不能创建新的节点
*/
//使用迭代法
public static TreeNode convertBST2DLLRec(TreeNode root) {
TreeNode cur = root;
if(cur==null) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode old = null;
TreeNode head = null;
while(true) {
while(cur!=null) {
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()) {
break;
}
cur = stack.pop();
if(old!=null) {
old.right = cur;
}
if(head==null) {
head = cur;
}
old = cur;
cur = cur.right;
}
return head;
}
/*
* 6.求二叉树第K层的节点数
*/
//1.迭代法
public static int getNodeNumKthLevel(TreeNode root, int k) {
TreeNode cur = root;
if(cur==null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(cur);
int i = 1;//表示当前二叉树的层数
int ccount = 1;//当前层的节点数
int ncount = 0;//下一层的节点数
while(!queue.isEmpty()&&i<k) {//开始遍历，到第K层截止
cur = queue.poll();
ccount--;
if(cur.left!=null) {
queue.offer(cur.left);
ncount++;
}
if(cur.right!=null) {
queue.offer(cur.right);
ncount++;
}
if(ccount==0) {
ccount = ncount;
ncount = 0;
i++;
}
}
return ccount;
}
/*2.利用递归求第K层的节点数:
* 如果二叉树为空获取k<1返回0
* 如果二叉树不为空并且k==1，返回1
* 如果二叉树不为空且k>1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和
*/
public static int getNodeNumKthLevel2(TreeNode root, int k) {
TreeNode cur = root;
if(cur==null||k<1) return 0;
if(k==1) return 1;
int left = getNodeNumKthLevel2(cur.left, k-1);
int right = getNodeNumKthLevel2(cur.right, k-1);
return left+right;
}
/*
* 7.求二叉树的叶子节点的个数,
*/
//1.利用迭代法
public static int getNodesNoChilds(TreeNode root) {
TreeNode cur = root;
if(cur==null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(cur);
int preNodes = 0;//记录上一层节点的个数
while(!queue.isEmpty()) {
cur = queue.poll();
if(cur.left!=null) {
queue.offer(cur.left);
}
if(cur.right!=null) {
queue.offer(cur.right);
}
//如果没有左孩子也没有右孩子，那该节点就是叶子结点
if(cur.left==null&&cur.right==null) {
preNodes++;
}
}
return preNodes;
}
//2.利用递归求叶子结点的数目
public static int getNodesNoChilds2(TreeNode root) {
TreeNode cur = root;
if(cur==null) return 0;
if(cur.left==null&&cur.right==null) return 1;
//将树拆分成左右两部分进行加和即可
return getNodesNoChilds2(cur.left) + getNodesNoChilds2(cur.right);
}
/*
* 8.判断两棵树是否是同一棵树,判断每个节点一样即可,这里使用的是迭代
*/
public static boolean isSame(TreeNode root1,TreeNode root2) {
TreeNode cur1 = root1;
TreeNode cur2 = root2;
if(cur1==null&&cur2==null) return true;
//有且只有一个树为空，那么他们肯定不同
if(cur1==null||cur2==null) return false;
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(cur1);
stack2.push(cur2);
while(!stack1.isEmpty()&&!stack2.isEmpty()) {
cur1 = stack1.pop();
cur2 = stack2.pop();
if(cur1==null&&cur2==null) {
continue;
} else if(cur1!=null&&cur2!=null&&cur1.val==cur2.val) {
stack1.push(cur1.right);
stack1.push(cur1.left);
stack2.push(cur2.right);
stack2.push(cur2.left);
} else {
return false;
}
}
return true;
}
/*
* 9.判断一棵树是否为平衡树,着手点：左右子树的高度相差不超过1,递归解法
*/
public static boolean isAVL(TreeNode root) {
TreeNode cur = root;
if(cur==null) return true;
if(Math.abs(getHight(cur.left)-getHight(cur.right))>1) {
return false;
}
return true;
}
/*
* 10.求二叉树的镜像，递归解法
*/
//1.加一个限制条件,直接在原树上进行改动
public static TreeNode mirrorCopy(TreeNode root) {
TreeNode cur = root;
if(cur==null) return null;
//交换左右子树
TreeNode left = mirrorCopy(cur.left);
TreeNode right = mirrorCopy(cur.right);
cur.left = right;
cur.right = left;
return cur;
}
//2.不对原树进行改动，返回一棵新树
public static TreeNode getMirrorTree(TreeNode root) {
if(root==null) return null;
TreeNode cur = new TreeNode(root.val);
cur.left = getMirrorTree(root.right);
cur.right = getMirrorTree(root.left);
return cur;
}
//3.判断两棵树是否互为镜像树
public static boolean isTwoMirrorTree(TreeNode root1,TreeNode root2) {
if(root1==null&&root2==null) return true;
if(root1==null||root2==null) return false;
//如果两棵树都不为空，则先比较两个根节点
if(root1.val!=root2.val) {
return false;
}
//递归比较两个根节点左右子树是否互为镜像
return isTwoMirrorTree(root1.left, root2.right)&&isTwoMirrorTree(root1.right, root2.left);
}
/*
* 11.判断树是否为完全二叉树,若二叉树的深度为h，那么除h层以外
* 其他层的节点都达到做大个数，第h层的所有节点都聚集在[最左边]（这一点以前没注意）
*/
public static boolean isCompleteBinaryTree(TreeNode root) {
if(root==null) return false;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
boolean result = true;
boolean mustHaveNoChild = false;
TreeNode cur;
while(!queue.isEmpty()) {
cur = queue.poll();
if(mustHaveNoChild) {
if(cur.left!=null||cur.right!=null) {
result = false;
break;
}
} else {
if(cur.left!=null&&cur.right!=null) {
queue.offer(cur.left);
queue.offer(cur.right);
} else if(cur.left!=null&&cur.right==null) {
queue.offer(cur.left);
mustHaveNoChild = true;
} else if(cur.left==null&&cur.right!=null) {
result = false;
break;
} else {
mustHaveNoChild = true;
}
}
}
return result;
}
/*
* 12.插入新节点
*/
public static TreeNode insertNode(TreeNode root,TreeNode node) {
if(root==null) return root;
TreeNode cur = root;
TreeNode last = null;
while(cur!=null) {
last = cur;
if(node.val<cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
if(last!=null) {
if(last.val>node.val) {
last.left = node;
} else {
last.right = node;
}
}
return root;
}
/*
* 13.求二叉树中结点的最大距离,即树中寻找相距距离最远的距离
* 利用递归的方法进行解答
*/
//封装的一个辅助结果类
public static class Result {
int maxDistance;
int maxDepth;
public Result() {
}
public Result(int maxDistance,int maxDepth) {
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
public static Result getMaxDistance(TreeNode root) {
if(root==null) {
Result empty = new Result(0, -1);
return empty;
}
//计算出左右子树分别的最大距离
Result lmd = getMaxDistance(root.left);
Result rmd = getMaxDistance(root.right);
Result res = new Result();
res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1;
res.maxDistance = Math.max(lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance));
return res;
}
/*
* 14.重建二叉树，根据前序遍历和中序遍历重建二叉树
*/
public static TreeNode rebuildBinaryTree(List<Integer> pre, List<Integer> in) {
TreeNode root = null;
List<Integer> leftPreOrder,rightPreOrder,leftInorder,rightInorder;
int inOrderPos,preOrderPos;
if(pre.size()!=0&&in.size()!=0) {
//将前序遍历的一个元素作为根节点
root = new TreeNode(pre.get(0));
//获取根节点在中序遍历中的索引
inOrderPos = in.indexOf(pre.get(0));
//获取左子树的遍历集合
leftInorder = in.subList(0, inOrderPos);
//获取右子树的遍历集合
rightInorder = in.subList(inOrderPos+1, in.size());
//获取左子树中序遍历的长度
preOrderPos = leftInorder.size();
//获取左子树在前序遍历序列中的字符串
leftPreOrder = pre.subList(1, preOrderPos+1);
//获取右子树在前序遍历序列中的字符串
rightPreOrder = pre.subList(preOrderPos+1, pre.size());
root.left = rebuildBinaryTree(leftPreOrder, leftInorder);
root.right = rebuildBinaryTree(rightPreOrder, rightInorder);
}
return root;
}
public static void main(String[] args) {
//树1
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n7.left = n8;
//树2
TreeNode m1 = new TreeNode(1);
TreeNode m2 = new TreeNode(2);
TreeNode m3 = new TreeNode(3);
TreeNode m4 = new TreeNode(4);
TreeNode m5 = new TreeNode(5);
TreeNode m6 = new TreeNode(6);
TreeNode m7 = new TreeNode(7);
m1.left = m2;
m1.right = m3;
m2.left = m4;
m2.right = m5;
m3.left = m6;
m3.right = m7;
//树1的镜像树
TreeNode p1 = new TreeNode(1);
TreeNode p2 = new TreeNode(3);
TreeNode p3 = new TreeNode(2);
TreeNode p4 = new TreeNode(7);
TreeNode p5 = new TreeNode(6);
TreeNode p6 = new TreeNode(5);
TreeNode p7 = new TreeNode(4);
p1.left = p2;
p1.right = p3;
p2.left = p4;
p2.right = p5;
p3.left = p6;
p3.right = p7;
// int len = getNodeNumber(n1);
// System.out.println("BinaryTreeLength:" + len);
//
// int len2 = getNodeNumber2(n1);
// System.out.println("BinaryTreeLength2:" + len2);
//
// int hight = getHight(n1);
// System.out.println("BinaryTreeHight:" + hight);
//
// int hight2 = getHight2(n1);
// System.out.println("BinaryTreeHight:" + hight2);
//
// System.out.print("preOrder:");
// preOrder(n1);
// System.out.println();
//
// System.out.print("midOrder:");
// midOrder(n1);
// System.out.println();
//
// System.out.print("posOrder:");
// posOrder(n1);
// System.out.println();
//
// System.out.print("preOrder2:");
// preOrder2(n1);
// System.out.println();
//
// System.out.print("midOrder2:");
// midOrder(n1);
// System.out.println();
//
// System.out.print("posOrder2:");
// posOrder2(n1);
// System.out.println();
//
// System.out.print("printBinary:");
// printBinary(n1);
// System.out.println();
//
// System.out.print("PrintBinary2:");
// printBinary2(n1);
//
// TreeNode cur = convertBST2DLLRec(n1);
// System.out.println("cur:" + cur);
// int k = 3;
// int kNodes = getNodeNumKthLevel(n1, k);
// System.out.println(k + "thNodes:" + kNodes);
//
// int kNodes2 = getNodeNumKthLevel2(n1,k);
// System.out.println(k + "thNodes2:" + kNodes2);
//
// int nodesNoChild = getNodesNoChilds(n1);
// System.out.println("BinaryTreeNoChilds:" + nodesNoChild);
//
// int nodesNoChild2 = getNodesNoChilds2(n1);
// System.out.println("BinaryNoChilds2:" + nodesNoChild2);
//
// boolean same = isSame(n1, m1);
// System.out.println("isSameTree:" + same);
//
// boolean avl = isAVL(n1);
// System.out.println("isAVL:" + avl);
// 这种方是直接在原树上进行改动的
// TreeNode mirrotNode = mirrorCopy(n1);
// System.out.print("mirrorTree:");
// printBinary(mirrotNode);
// System.out.println();
// //获取二叉树的镜像，创建一棵新的镜像树返回
// TreeNode mirrorTree = getMirrorTree(n1);
// System.out.print("mirror:");
// printBinary(mirrorTree);
// System.out.println();
// //查看当前树是否被改动
// System.out.print("src:");
// printBinary(n1);
// System.out.println();
// boolean isTwoMirror = isTwoMirrorTree(n1, p1);
// System.out.println("isTwoMirror:" + isTwoMirror);
// boolean complete = isCompleteBinaryTree(n1);
// System.out.println("isCompleteBinaryTree:" + complete);
// System.out.print("srcTree:");
// printBinary(n1);
// TreeNode insert = new TreeNode(2);
// TreeNode insertNode = insertNode(n1, insert);
// System.out.println();
// System.out.print("afterInsert:");
// printBinary(insertNode);
// System.out.println();
Result res = getMaxDistance(n1);
System.out.println("res:" + "res.maxDepth=" + res.maxDepth + " res.maxDistance=" + res.maxDistance);
}
}
【补充】
二叉树的遍历
public static void preOrder(BinaryTree root){ //先根遍历
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}
public static void inOrder(BinaryTree root){ //中根遍历
if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}
public static void postOrder(BinaryTree root){ //后根遍历
if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}
上面使用的是递归算法，下面看一下java中常用的使用队列如何遍历一棵树（从上到下，同一层从左到右）
//二叉树的遍历，从上到下，同一层的从左到右
//二叉树的定义
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
//遍历所有元素并返回
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
TreeNode cur = root;
ArrayList<Integer> list = new ArrayList<Integer>();
if(cur==null) return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//向队列中添加一个树节点并返回true,如果队列已满则返回false
//这里面是放的树的根节点，且包含左右子节点，所以这里不仅仅放了一个节点
//实则放进去了整个一棵树
queue.offer(cur);
while(!queue.isEmpty()) {
//移除并返问队列头部的元素,如果队列为空,则返回null，这里仅仅是拿掉一个节点
cur = queue.poll();
list.add(cur.val);
if(cur.left!=null) {
queue.offer(cur.left);
}
if(cur.right!=null) {
queue.offer(cur.right);
}
}
return list;
}
9.1输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果
public class Solution {
/*
思路：后序遍历的二叉树根节点必定在数组的末位，前半部分为
根节点的左子树，后半部分为根节点的右子树，其中左子树的元素必定
都小于根节点，否则必定不满足二叉搜索树的定义；同理右子树的元素
必定都大于根节点的元素，否则不满足，递归即可
*/
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0)
return false;
return isBST(sequence,0,sequence.length-1);
}
public boolean isBST(int [] sequence,int start,int end) {
if(start>=end) return true;
//遍历左子树，一旦出现大于根节点的元素说明，左子树遍历结束，再遍历右子树
int i = start;
for (; i < end; i++) {
if(sequence[i] > sequence[end]) break;
}
//左子树遍历结束，右子树开始遍历
for (int j = i; j < end; j++) {
if(sequence[j] < sequence[end]) return false;
}
return isBST(sequence, start, i-1)&&isBST(sequence, i, end-1);
}
}
9.2打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
public class Solution {
//存放所有了路径
ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
//存放单个满足条件的路径
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
TreeNode cur = root;
if(cur==null) return listAll;
list.add(cur.val);
target = target - cur.val;
//如果为遍历的节点之和已经达到了指定值并且当前节点是叶子结点，则将该路径存入ListAll中
if(target==0&&cur.left==null&&cur.right==null) {
listAll.add(new ArrayList(list));
}
//递归遍历左子树
FindPath(cur.left,target);
//递归遍历右子树
FindPath(cur.right,target);
//删除该节点，返回到父节点
list.remove(list.size()-1);
return listAll;
}
}
package com.hhu.sort;
import java.util.HashMap;
import java.util.Stack;
public class Demo {
private static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public static void printList(Node head) {
while(head!=null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
//查询链表长度
public static int getListLength(Node head) {
int len = 0;
Node temp = head;
while(temp!=null) {
len++;
temp = temp.next;
}
return len;
}
//反转链表(高频考点!!!),时间复杂度为O（n）,方法一
public static Node reverseList(Node head) {
//如果链表为空或者只有一个元素，那么原路返回，不需要反转
if(head==null||head.next==null) {
return head;
}
Node reHead = null;//定义一个链表存放逆序的链表
Node cur = head;//用temp链表来进行所有操作，不影响原来的链表
//进行链表反转，注意这里的写法
while(cur!=null) {//相当于将当前的节点往前插入
Node preCur = cur;
cur = cur.next;
preCur.next = reHead;
reHead = preCur;
}
return reHead;
}
//反转链表，方法二：递归
public static Node reverseListRec(Node head) {
if(head==null||head.next==null) {
return head;
}
Node reHead = reverseListRec(head.next);
head.next.next = head;
head.next = null;
return reHead;
}
/*查找链表中的倒数第K个节点,思路：定义两个指针，从最开始的下标开始，
* 两个指针向前移动，但是要让移动的指针先后移动的指针移动K个单位，这样当第一个
* 指针到达链表末尾的时候，后移动的指针所在的未知就是指向倒数第K个节点
*/
public static Node reGetKthNode(Node head,int k) {
if(k==0||head==null) {
return null;
}
Node q = head;
Node p = head;
while(k>1&&q!=null) {//这里先让q指针先移动
q = q.next;
k--;
}
if(k>1||q==null) {//链表的长度小于K
return null;
}
while(q.next!=null) {//两个指针此时一起移动，q指针已经领先p指针K个单位
p = p.next;
q = q.next;
}
//出了循环，p指向的位置就是倒数第K个节点
return p;
}
/*
* 递归打印倒数第K位的值
*/
static int level = 0;
public static void reGetKthNodeRec(Node head,int k) {
if(head==null) {
return;
}
reGetKthNodeRec(head.next,k);
level++;
if(level==k) {
System.out.println(head.data);
}
}
/*查找单链表的中间节点,思路：和上面查找倒数第K个节点的思路很像，
* 这里可以这样搞，同时定义两个指针，这里可以让他们两个同时移动，其中
* 一个指针每次移动1个单位长度，另一个指针每次移动2个单位长度,当后者移动到
* 链表末尾的时候，那么前者所在的位置就是链表的中间点
*/
public static Node getMiddleNode(Node head) {
if(head==null||head.next==null) {
return head;
}
Node q = head;
Node p = head;
while(q.next!=null) {//q移动两个长度单位，p移动一个单位长度
q = q.next;
p = p.next;
if(q.next!=null) {//q再走一步，
q = q.next;
}
}
return p;
}
/*
* 从尾到头打印单链表，对于这种颠倒的问题，要么使用栈（先进后出）,要么让
* 系统使用栈：递归,注意链表为空的情况
* 时间复杂度为O（n）
*/
//方法一：使用栈Stack
public static void reversePrintListStack(Node head) {
Stack<Node> s= new Stack<Node>();
Node cur = head;
while(cur!=null) {
s.add(cur);
cur = cur.next;
}
while(!s.isEmpty()) {
cur = s.pop();
System.out.print(cur.data + " ");
}
System.out.println();
}
//方法二：使用递归，优雅的方式
public static void reversePrintListRec(Node head) {
if(head==null) {
return;
} else {
//顺序
reversePrintListRec(head.next);
System.out.print(head.data + " ");
}
}
/*
* 合并两个有序的链表，且使他们依然有序(高频考点!!!)
* 类似于归并，方法一
*/
public static Node mergeSoertList(Node head1,Node head2) {
//有一个链表为空的情况，则直接返回另一个链表即可
if(head1==null) {
return head2;
}
if(head2==null) {
return head1;
}
//创建一个空的链表用来归并两个链表
Node mergeHead = null;
//首先将根节点选出来
if(head1.data<head2.data) {
mergeHead = head1;
head1 = head1.next;
mergeHead.next = null;
} else {
mergeHead = head2;
head2 = head2.next;
mergeHead.next = null;
}
Node mergeCur = mergeHead;
//开始遍历
while(head1!=null&&head2!=null) {
if(head1.data<head2.data) {
mergeCur.next = head1;
head1 = head1.next;
mergeCur = mergeCur.next;
mergeCur.next = null;
} else {
mergeCur.next = head2;
head2 = head2.next;
mergeCur = mergeCur.next;
mergeCur.next = null;
}
}
//合并剩余元素
if(head1!=null) {
mergeCur.next = head1;
} else {
mergeCur.next = head2;
}
return mergeHead;
}
//方法二：递归合并
public static Node mergeSortedLisrRec(Node head1,Node head2) {
if(head1==null) {
return head2;
}
if(head2==null) {
return head1;
}
Node mergeHead = null;
if(head1.data<head2.data) {
mergeHead = head1;
mergeHead.next = mergeSortedLisrRec(head1.next, head2);
} else {
mergeHead = head2;
mergeHead.next = mergeSortedLisrRec(head1, head2.next);
}
return mergeHead;
}
/*
* 判断单链表是否有环,思路：有环的话说明一个指针去遍历的话，是援用走不到头的
* 因此可以使用两个指针去遍历，一个指针每次走一步，一个指针一次走两步，
* 如果有环的话，那么两个指针肯定会在环中相遇
*/
public static boolean hasCycle(Node head) {
Node fast = head;
Node slow = head;
while(fast!=null&&fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
if(fast==slow) {//两个指针相遇，链表中存在环
return true;
}
}
return false;
}
/*
* 判断两个单链表是否相交，思路：只要两个链表相交，那么必定从某个节点开始一直到最后
* 他们两个链表的节点都是相同的，共同点，只要最后的一个节点相同即可
*/
public static boolean isIntersect(Node head1,Node head2) {
if(head1==null||head2==null) {
return false;
}
Node tail1 = head1;
while(tail1.next!=null) {
tail1 = tail1.next;
}
Node tail2 = head2;
while(tail2.next!=null) {
tail2 = tail2.next;
}
return tail1 ==tail2;
}
/*
* 求两个单链表相交的第一节点,思路：对第一个链表遍历，计算长度len1,保存末尾节点
* 遍历第二个链表遍历，计算长度len2，同时检测末尾节点是否和第一个链表的末尾节点相同
* 若果不相同，则不相交
*
* 然后两个链表均从表头开始，假设len1>len2
* 那么将第一个链表先遍历len1-len2个节点，然后两个链表再同时遍历剩余的
* 元素,直到两个节点的地址相同
*/
public static Node getFirstCommonNode(Node head1,Node head2) {
if(head1==null||head2==null) {
return null;
}
int len1 = 1;
Node tail1 = head1;
while(tail1.next!=null) {
tail1 = tail1.next;
len1++;
}
int len2 = 1;
Node tail2 = head2;
while(tail2.next!=null) {
tail2 = tail2.next;
len2++;
}
//不相交的话直接返回NULL
if(tail1!=tail2) {
return null;
}
Node n1 = head1;
Node n2 = head2;
if(len1>len2) {
int k = len1 - len2;
while(k!=0) {
n1 = n1.next;
k--;
}
} else {
int k = len2 - len1;
while(k!=0) {
n2 = n2.next;
k--;
}
}
//一起向后遍历，找到交点
while(n1!=n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
/**
* 给出一单链表头指针head和一节点指针toBeDeleted，O(1)时间复杂度删除节点tBeDeleted
* 对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点
* ，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，
* 链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点
* ，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)
*/
public static void delete(Node head,Node toDelete) {
if(toDelete==null) {//待删除节点为空节点
return;
}
if(toDelete.next!=null) {//待删除的节点不是末位节点
toDelete.data = toDelete.next.data;
toDelete.next = toDelete.next.next;
} else {
if(head==toDelete) {//待删除节点为头节点
head = null;
} else {//待删除节点为链表中的常规节点
Node node = head;
while(node.next!=toDelete) {
node = node.next;
}
node.next = null;
}
}
}
public static void main(String[] args) {
Node n1 = new Node(2);
Node n2 = new Node(4);
Node n3 = new Node(6);
Node n4 = new Node(8);
Node n5 = new Node(10);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
Node m1 = new Node(1);
Node m2 = new Node(3);
Node m3 = new Node(4);
Node m4 = new Node(7);
Node m5 = new Node(9);
m1.next = m2;
m2.next = m3;
m3.next = m4;
m4.next = m5;
Node p1 = new Node(1);
Node p2 = new Node(3);
Node p3 = new Node(4);
Node p4 = new Node(7);
Node p5 = new Node(9);
p1.next = p2;
p2.next = p3;
p3.next = p4;
p4.next = p2;
Node w1 = new Node(1);
Node w2 = new Node(3);
Node w3 = new Node(4);
Node w4 = new Node(7);
Node w5 = new Node(9);
w1.next = w2;
w2.next = w3;
w3.next = n2;
Node d1 = new Node(2);
Node d2 = new Node(4);
Node d3 = new Node(6);
Node d4 = new Node(8);
Node d5 = new Node(10);
d1.next = d2;
d2.next = d3;
d3.next = d4;
d4.next = d5;
//打印节点
System.out.print("打印链表：");
printList(n1);
//查询链表长度
System.out.print("链表长度：");
System.out.println(getListLength(n1));
// //反转链表
// Node reverse = reverseList(n1);
// System.out.print("反转链表:");
// printList(reverse);
// //反转链表
// Node reverse2 = reverseListRec(n1);
// System.out.print("反转链表(方法二):");
// printList(reverse2);
//获取倒数第K个节点
int k = 2;
Node rek = reGetKthNode(n1, k);
System.out.print("倒数第"+k+"个节点：");
printList(rek);
//递归打印第K位的值
int k1 = 1;
System.out.print("递归打印第"+ k1 + "位的值：");
reGetKthNodeRec(n1, k1);
//获取链表的中间节点
Node middle = getMiddleNode(n1);
System.out.print("获取中间节点：");
printList(middle);
//从尾到头打印链表
System.out.print("从尾到头打印链表(方法一使用栈):");
reversePrintListStack(n1);
//方法二用递归实现
System.out.print("从尾到头打印链表(方法二使用递归):");
reversePrintListRec(n1);
System.out.println();
//拼接两个有序链表，使之仍然有序(这里不能拼接有环的链表，否则死循环)
Node mergeNode = mergeSoertList(n1, m1);
System.out.print("拼接两个有序链表使之仍然有序：");
printList(mergeNode);
// //方法二用递归的方法合并（递归有问题）
// Node merge2 = mergeSortedLisrRec(n1, m1);
// System.out.print("拼接两个有序链表使之仍然有序(方法二使用递归)：");
// printList(merge2);
//判断链表中是是否有环
boolean t = hasCycle(p1);
System.out.print("判断链表中是否有环：" + t);
System.out.println();
//判断两个链表是否有相交点
boolean t2 = isIntersect(n1, w1);
System.out.print("判断两个链表是否有相交点:" + t2);
System.out.println();
//求相交链表的相交节点
Node common = getFirstCommonNode(n1, w1);
System.out.print("求相交链表的相交节点：");
printList(common);
//删除节点
System.out.println("进行节点删除");
System.out.print("原链表：");
printList(d1);
delete(d1, d4);
System.out.print("删除后的链表:");
printList(d1);
}
}
package com.java24hours.mianshibaodian;
import java.util.Scanner;
public class SnakeJuZhen {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
StringBuilder builder = new StringBuilder();
for(int i=1;i<=n;i++) {
for(int j=1,start=(i-1)*i/2+1,step=i+1;j<=n-i+1;j++,start += step,step++) {
builder.append(start).append(' ');
}
//设置换行符
builder.setCharAt(builder.length()-1, '\n');
}
System.out.println(builder.toString());
}
}
}
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法.
【解析】思路：比较倾向于找规律的解法，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5， 可以总结出f(n) = f(n-1) + f(n-2)的规律，即斐波那契数列。但是为什么会出现这样的规律呢？假设现在6个台阶，我们可以从第5跳一步到6，这样的话有多少种方案跳到5就有多少种方案跳到6，另外我们也可以从4跳两步跳到6，跳到4有多少种方案的话，就有多少种方案跳到6，其他的不能从3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。
//方法一：
public class Solution {
public int JumpFloor(int target) {
if(target==0||target==1||target==2){
return target;
} else {
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
}
[拓展]这里如果一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
【思路】这么多的台阶，除了最后一个台阶必须跳之外的所有台阶，青蛙都有跳与不跳的两种选择，所以共有2^(n-1)种跳法。但是这种思路不能用在第一个题中，第一题中的台阶没有那么轻松
public class Solution {
public int JumpFloor(int target) {
//注意这里的Math.pow(x,y)是求幂运算，返回值为double，强转
return (int)(Math.pow(2,target-1));
}
}
树结构中的几个定义：
二叉树中
定义：一种左、右子树的高度差不超过1的二叉排序树。2个点需要注意的是：
对应的也有最小不平衡子树：距离新插入节点最近的子树、且平衡因子（即左子树的高度-右子树的高度）绝对值大于1的子树。
为了在插入过程中，保证二叉排序树的平衡性，需要适当对最小不平衡树进行左旋或右旋，下面构建一棵平衡二叉树的过程，依次插入的节点值为{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}：
注：最后一步中，先调节成平衡因子正负相同的新子树A，然后再调节由原来的最小不平衡树B和调整得到新子树A组成得到的新子树C（由子树A和5、6两个数值组成的新子树C），而不是调节下面已经调正为平衡因子正负相同的子树A。
定义：每个节点的孩子数可以多于2个，且每个节点处可以存储多个元素。多路查找树之间存在特定的排序关系，多路查找树又有4种特殊的形式：2-3树、2-3-4树、B树、B+树。
定义：每个节点上都具有2个孩子（该节点称之为2节点）或者3个孩子（该节点称之为3节点）。注：
所有2-3树的叶子节点都在同一层上，下面是一棵标准的2-3树：
定义：其实就是2-3树的扩展，扩展出一个4节点（包含3个元素和4个孩子或没有孩子）的使用，对于4节点：含有3个小（如A）、中（如B）、大（如C）元素，如果存在4个孩子，那左子树包含所有小于最小元素A的内容，第二子树包含所有 A < x < B 之间的内容x，第三子树包含所有 B< x < C 之间的内容x，第四子树包含所有 x > C 的内容。
B树是一种平衡的多路查找树，上述的2-3树和2-3-4树都是B树的特例，节点最大的孩子数目称之为B树的阶，很明显上述的2-3树的阶为3，2-3-4树的阶为4。作为一棵阶数为 m 的B树，具备如下的特性：
B树的典型应用场景：硬盘是将所有的信息分割为大小相等的页面，每次硬盘都是读写一个或多个完整的页面（对于硬盘来说，一页的长度可能是211-214个字节），要处理的硬盘数据量很大，无法一次性全部装入内存，因此需要对B树进行调整，使得B树的阶阶数（或者节点元素）与硬盘的页面大小相匹配。在有限内存的情况下，可以在一次访问中获得最大数据量。
B树中，会往返于每个节点之间，意味着在硬盘的页面之间进行多次访问，如将B树种的每个节点视作硬盘的不同页面，为了遍历B树，每次经过节点遍历时，都需要对节点中的元素进行一次遍历，这样的重复遍历的行为导致遍历的效率很低。这种诉求就会导致我们思考有没有可能在遍历时每个元素只遍历一次，B+树就是在原有B树的基础上，增加了新的元素组织方式。在B+树中，出现在分支节点中的元素会被当做他们在该分支节点位置的中序后继者（叶子节点）中再次列出，此外，每个叶子节点都会保存一个指向后一个叶子节点的指针。下面是一棵B+树（黄色节点值会在叶子节点中再次列出，且所有的叶子节点都是连接在一起的）：
一棵m阶的B+树和m阶的B树差异在于：
B+树的数据结构的好处在于，若要随机查找，就可以从根节点出发，和B树的查找方式相同，只不过即使在分支节点找到待查找的关键字，它也仅仅用来索引的，而不能提供实际记录的访问，最终还是要到达包含该关键字的终端节点。
若需要从最小关键字进行从小到大的顺序查找，就可以从最左侧的叶子节点出发，不经过分支节点，而是沿着指向下一叶子的指针就可以遍历所有的关键字。B+树比较适合带有范围的查找，比如需要查找18到22之间的数，就可以从根节点出发找到第一个18的数，然后再从叶子节点按顺序查找到所有符合要求的数。B+树的插入、删除也和B树类似，只是都是在叶子节点上进行而已。
散列技术：在查找关键字时，不需要比较就可以获取记录的存储位置，而是通过某个函数存储位置=f(关键字)来直接获取。散列技术就是在记录的存储位置和它的关键字之间建立一个对应关系f，使得每个关键字key对应一个存储位置f(key)。上述描述的函数f就是散列函数（又称哈希函数）。采用散列技术将记录存储在一块连续的存储空间中，那这块连续的存储空间称为散列表或哈希表，关键字对应的记录存储位置我们称之为散列地址。
散列表的过程描述很简单：
所以这个层面上散列技术既是存储方法，也是查询方法。散列主要是面向查找的数据结构，它最适合的场景是查找与给定值相等的记录，简化了查找的过程，所以查找的效率很高，但同事散列技术也不具备很多常规数据结构的能力，像一个关键字对应多条记录、范围查询都不是散列表可以高效率完成的。
在散列技术中，通过上述的描述可以确定散列函数的很重要，它会影响查找效率，再有一个，散列函数的冲突必须要解决，即可能出现不同关键字对应着同样的散列地址（f(x1)=f(x2)），x1和x2称之为散列函数的同义词。
一个好的散列函数应该具备如下素质：
下面是一些常见的散列函数：
直接取关键字的某个线性函数值为散列地址，即f(x)=a*x+b（a、b为常数）的形式，这样的散列函数就为直接定址法，这种方式简单、均匀、无冲突，但需要事先知道关键字的分布情况，适合查找较小且连续的场景，所以这种方式虽然简单，但实际很少用。
【示例】
统计不同年份的人数，事先知道1980年有1500W、1981年有1600W……那可以使用f(x)=x*1-1980来计算地址。
如果关键字的位数较多，如11位的手机号，其实只有后4位才是用户号（前7位都是一些其他信息，不同用户的前7位也可能相同），如果需要存储以手机号为关键字的一些记录，那可以直接使用后4位作为散列地址啊，如果使用后4位还出现冲突，可以对这4位再进行处理（反转、左环位移、右环唯一等等），总之为的是提供一个散列函数，可以合理的将关键字分配到散列表中。
场景：抽取关键字的部分来计算散列地址，数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干分较均匀，可以考虑这种方式。
见名之意，直接将关键字平方，取中间的某几位作为关键字（如1234平方为1522756取中间3位227、4321平方为18671041取中间3位671或710）。平方取中法适用于不知道关键字的分布，而位数不是很大的情况。
将关键字从左到右分割成位数相等的几部分（最后一部分位数不够可以稍微短点），然后将这几部分分叠加求和，并按散列表表长，取后几位作为散列地址。如关键字为9876543210，散列表表长为3位，将关键字分为4组：987、654、321、0，叠加求和987+654+321+0=1962，取后3位962作为散列地址，如果不能均匀分布，可以将部分数字反转。折叠法不需要事先知道关键字的分布，适合关键字位数较多的情况。
除留余数法是散列函数最常使用的方式，即取关键字的模取余，关键是确定除数的数值（即f(x) = |x| % a，a为常数）。这种方式是可能存在冲突的，对于上述 a 的取值有建议：a为小于或等于表长（最好接近表长）的最小质数或不包含小于20质因子的合数。
即散列函数为f(x) = random(x)，当关键字长度不等时，可以采用这种方式，如果遇到非数字，可以统一转成ASCII或其他。
总结
散列函数的构造需要考虑的因素有：
散列冲突即前面所讲的散列函数在x1≠x2时出现了f(x1) = f(x2)的情况，解决这种冲突也有一些常用的方式。
定义：在发生冲突时，就去寻找下一个空的散列地址，只要散列表足够大，就可以找到空的散列地址，再将记录存入即可。开放定址法的规则为f1(x) = (f1(x) + d) % m，其中m表示表长，d表示的是1,2,3,……,m-1（当f(x)已存在元素则会依次增加这个d）。如待存储的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，那表长 m=12，散列函数采用除留余数法f2(x)= x % 12，那对应上述关键字的散列地址为{0,7,8,4,1,1……}，发现在关键字25和37处得出的散列地址都为1，出现了冲突，那在计算37的散列地址时应该解决这个冲突：f1(37) = (f2(37) + 1) % 12 = 2，一看地址2上没有元素，那37直接存储到地址2上，整个过程如下图：
上述的过程是开放定址法的整个过程，又形象的称之为线性探测法。中间出现冲突的场景称之为堆积，堆积的一旦出现就需要不断的处理冲突，解决冲突将会导致效率的降低，尤其是当出现堆积时，空位出现在前面而非后面时（如上述示例中的34），就要先把它后面的位置都探测一遍，发现都被占用了，然后再从头探测，一直探测到下标为9的位置，为了改善这种情况，可以将开放定址方法中的d参数改进为12,-12,22,-22,……,q2,-q2，其中q<=m/2。将这种以平方的方式称之为二次探测法，二次探测法可以避免让关键字都聚集在某一块区域。当然，关于d变量的改进方式还有其他的，比如将其改进为一个随机函数，此时就叫随机探测法。
再散列法就是在发生冲突时，再换一种散列函数，如果还冲突，接着换，知道找到空位为止，这就需要事前准备多个散列函数，这样可以使得关键字不聚集，但会增加计算时间。
链接地址法可以在有冲突的地方，将所有在同一位置冲突的关键字存储在一个单链表（同义词子表，我们把冲突的关键字都叫同义词）中。以开放定址法中的示例为例，就会出现下面的数据结构：
在散列表中只存储同义词子表的头指针，当出现冲突时就给同义词子表添加节点即可。链地址法对于可能出现很多冲突的散列函数而言，提供了绝不会出现找不到地址的保障，但也带来了查找时需要遍历单链表的性能损耗。
在冲突发生时，将这些冲突的关键字都放在一个叫做公共的溢出区的地方存储，还是之前的示例就变成下面的数据结构
原来出现冲突的48、37、34三个关键字直径丢进溢出区即可。在查找时，先到基本表中查找对比，如果相等则成功，如果不相等则到溢出表中查找。若冲突数据较少的情况下，公共溢出区的结构对查找性能还是非常高的。