二叉树
非递归遍历
前序
/**
* 先序非递归遍历
* 访问一个节点时候,若该节点左右孩子节点都存在,按照右孩子左孩子顺序压栈,若只存在一个孩子节点,直接压栈该孩子节点
*/
public void firstTravel(TreeNode root) {
Stack<TreeNode> stack =
new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val +
" ");
if (node.right !=
null)
stack.push(node.right);
if (node.left !=
null)
stack.push(node.left);
}
System.out.println();
}
中序
/**
* 中序非递归遍历
* 思想:
* 左-根-右:所以只要左孩子还有左子树就要先遍历左孩子的左子树
* 1、从根节点开始将左孩子节点压栈,如果左孩子节点还有左子树继续将左孩子节点的左孩子节点压栈,一直这么持续操作,直到遇到null节点;
* 2、此时栈顶节点就是该树(不特指整棵树)中序遍历第一个要访问的节点,弹出该节点;
* 3、对该节点的右孩子节点重复1,2操作。
*/
public void inTravel(TreeNode root) {
Stack<TreeNode> stack =
new Stack<>();
TreeNode node = root;
while (node !=
null || !stack.isEmpty()) {
if (node !=
null) {
stack.push(node);
node = node.left;
}
else {
node = stack.pop();
System.out.print(node.val +
" ");
node = node.right;
}
}
System.out.println();
}
后序
/**
* 后续遍历非递归
*/
public void lastTravel(TreeNode root) {
Stack<TreeNode> stack =
new Stack<>();
TreeNode node = root;
TreeNode pre =
null;
while (!stack.isEmpty() || node !=
null) {
if (node !=
null) {
stack.push(node);
node = node.left;
}
else {
node = stack.pop();
if (node.right ==
null || pre == node.right) {
System.out.print(node.val +
" ");
pre = node;
node =
null;
}
else {
stack.push(node);
node = node.right;
}
}
}
System.out.println();
}
层次
public List<List<Integer>>
levelOrder(TreeNode root) {
List<List<Integer>> res =
new ArrayList<List<Integer>>();
LinkedList<TreeNode> q =
new LinkedList<TreeNode>();
if(root ==
null)
return res;
TreeNode p = root;
q.addLast(p);
while(!q.isEmpty()){
int tmpSize = q.size();
List<Integer> tmpList =
new ArrayList<Integer>();
for(
int i=
0;i<tmpSize;i++){
p = q.getFirst();
q.poll();
tmpList.add(p.val);
if(p.left!=
null) q.addLast(p.left);
if(p.right!=
null) q.addLast(p.right);
}
res.add(tmpList);
}
return res;
}
排序
快排
public static int partition(
int[] numbers,
int low,
int high) {
int temp = numbers[low];
while(low < high) {
while(low < high && numbers[high] >= temp) high--;
numbers[low] = numbers[high];
while(low < high && numbers[low] <= temp) low++;
numbers[high] = numbers[low] ;
}
numbers[low] = temp ;
return low ;
}
public static void quickSort(
int[] numbers,
int low,
int high) {
if(low < high) {
int middle = partition(numbers,low,high);
quickSort(numbers, low, middle-
1);
quickSort(numbers, middle+
1, high);
}
}
希尔
int[] arrary = {
49,
38,
65,
97,
76,
13,
27,
49,
55,
04};
int[] dk = {
5,
3,
1};
public void shellInsert(
int[] array,
int dk) {
int temp =
0, j =
0;
for (
int i = dk; i < array.length; i++) {
if (array[i] < array[i - dk]) {
temp = array[i];
for (j = i - dk; j >=
0 && temp < array[j]; j -= dk) {
array[j + dk] = array[j];
}
array[j + dk] = temp;
}
}
}
public void shellSort(
int[] array,
int[] dk,
int t) {
for (
int i =
0; i < t; i++) {
shellInsert(array, dk[i]);
}
}
归并
public void mergeSort(
int[] data) {
if (data ==
null || data.length ==
0)
return;
int len = data.length;
int[] temp =
new int[len];
mergeSortCore(data,
0, len -
1, temp);
}
public void merge(
int[] data,
int start,
int mid,
int end,
int[] temp) {
int i = start, j = mid +
1, k =
0;
while (i <= mid && j <= end) {
if (data[i] < data[j])
temp[k++] = data[i++];
else
temp[k++] = data[j++];
}
while (i <= mid)
temp[k++] = data[i++];
while (j <= end)
temp[k++] = data[j++];
for (i =
0; i < k; i++)
data[start + i] = temp[i];
}
public void mergeSortCore(
int[] data,
int start,
int end,
int[] temp) {
if (start == end)
return;
int mid = (start + end) /
2;
mergeSortCore(data, start, mid, temp);
mergeSortCore(data, mid +
1, end, temp);
merge(data, start, mid, end, temp);
}
栈
括号匹配
public boolean matchJudge(String str) {
HashMap<Character, Character> dict =
new HashMap<>();
dict.put(
'(',
')');
dict.put(
'[',
']');
dict.put(
'{',
'}');
Stack<Character> stack =
new Stack();
boolean res =
false;
int len = str.length();
char ch =
'\0';
char p =
'\0';
for (
int i =
0; i < len; i++) {
ch = str.charAt(i);
if (dict.containsKey(ch))
stack.push(ch);
else if (dict.containsValue(ch)) {
if (!stack.isEmpty() && dict.get(stack.peek()) == ch)
stack.pop();
else return false;
}
}
return stack.isEmpty() ?
true :
false;
}
public String
getMatchData(
int index) {
String str =
"";
String str1 =
"{[(1+2)/(3+4)]-[[(1+2)/(3+4)]]}";
String str2 =
"{[()]}";
String str3 =
"{[]]}";
String str4 =
"[()(]";
String str5 =
"([)]";
String str6 =
"({}[]]])";
String str7 =
"[()](((";
switch (index) {
case 1: { str = str1;
break; }
case 2: { str = str2;
break; }
case 3: { str = str3;
break; }
case 4: { str = str4;
break; }
case 5: { str = str5;
break; }
case 6: { str = str6;
break; }
case 7: { str = str7;
break; }
}
return str;
}