1.中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null) return list;
TreeNode p = root;
while(p != null) {
stack.push(p);
p = p.left;
}
while(!stack.isEmpty()) {
TreeNode q = stack.pop();
list.add(q.val);
TreeNode k = q.right;
while(k != null) {
stack.push(k);
k = k.left;
}
}
return list;
}
}
2.前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null) return list;
TreeNode p;
stack.push(root);
while(!stack.isEmpty()) {
p = stack.pop();
list.add(p.val);
//栈先入后出，所以先压右边
if(p.right != null) {
stack.push(p.right);
}
if(p.left != null) {
stack.push(p.left);
}
}
return list;
}
}
3.后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node.left != null) stack.push(node.left);//和传统先序遍历不一样，先将左结点入栈
if(node.right != null) stack.push(node.right);//后将右结点入栈
res.add(0,node.val); //逆序添加结点值
}
return res;
}
}
4.层次遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
List<Integer> list = new ArrayList<>();
int size = q.size();
for(int i = 0; i < size; i++){
TreeNode cur = q.poll();
list.add(cur.val);
if(cur.left != null) q.offer(cur.left);
if(cur.right != null) q.offer(cur.right);
}
res.add(list);
}
return res;
}
}
排序和查找见下方链接
https://blog.csdn.net/m0_37990703/article/details/78184305
5.选择排序
思路：在乱序数组中，假设第一位数最小，依次让后面的数与之比较，若遇到比它小的数就交换位置，一趟下来第一个数就是序列中最小的数，然后从第二个数开始重复操作。
public static void selectSort(int[] array) {
int temp;
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[i]) {
temp = array[j];
array[j] = array[I];
array[i] = temp;
}
}
}
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + " ");
}
}
6.插入排序
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
for (; j >= 0 && array[j] > temp; j--) {
//将大于temp的值整体后移一个单位
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + " ");
}
}
7.shell排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
先取一个正整数d1 < n, 把所有相隔d1的记录放一组，每个组内进行直接插入排序；然后d2 < d1，重复上述分组和排序操作；直至di = 1，即所有记录放进一个组中排序为止。
public static void shellSort(int[] arr) {
int len = arr.length;
// 所有的步长可能性（首次为数组长的一半，接下来每次为上一次的一半）
for (int gap = len / 2; gap > 0; gap /= 2) {
// 将步长中的所有元素进行插入排序
for(int w = 0; w < gap; w++){
// 步长为gap的插入排序
// 对照插入排序
/*
* for(int i = p + 1; i < r; i++){
* int key = arr[I];
* int j = i - 1;
* while(j >= 0 && arr[j] > key) {
* arr[j + 1] = arr[j];
* j--;
* }
* arr[j + 1] = key;
* }
*/
for (int i = gap + w; i < len; i += gap) {
// 插入排序
int key = arr[I];
int j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + " ");
}
}
8.冒泡排序
思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
代码：
public static void bubbleSort(int[] array) {
int temp = 0;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(array) + " bubbleSort");
}
9.快速排序
快速排序是排序方法里面速率最快的一种方法，是对冒泡排序的一种改进， 属于不稳地排序。
public static void main(String []args) {
int[] array = new int[]{1,4,5,2,3,5};
quickSort(array, 0, array.length-1);
System.out.print(Arrays.toString(array));
}
public static void quickSort(int a[],int start,int end)//start是每次快速排序的数组开始下标，end是结束下标
{
if(start>end)
{
return;
}
int startNum=a[start];
int left=start;//left是左标记的下标
int right=end;//right是右标记的下标
while(left < right)
{
//当左标记在右标记的左边并且右标记的数比左标记的数大时
while(left<right&&a[right]>=a[start])
{
right--;//右边标记左移
}
while(left<right&&a[left]<=a[start])
{
left++;//左边标记右移
}
int temp=a[left];//交换左边右边数的操作
a[left]=a[right];
a[right]=temp;
}
a[start]=a[right];//将中间数交换到左右标记相遇的地方
a[right]=startNum;
quickSort(a,right+1,end);//对中间数左边的数组进行递归快速排序
quickSort(a,start,right-1);//对中间数右边的数组进行递归快速排序
}
10.二分查找
private static int myBinarySearch(int [] array , int k) {
int low = 0;
int high = array.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(array[mid] == k) {
return mid;
} else if(array[mid] < k) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
网友评论