2023-09-13
467
原创
Java数据结构和算法(代码版)-1
Java数据结构和算法(代码版)-1
二分查找
package com.lzlg.study.algorithm.new2023.binarysearch;
import java.util.Arrays;
/
* @author lzlg
* 2023/7/16 10:42
*/
public class BinarySearchTest {
public static void main(String[] args) {
int[] array = {1, 2, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 9};
int target = 5;
System.out.println(binarySearchLeftIndexMost(array, target));
System.out.println(binarySearchRightIndexMost(array, target));
}
/
* 二分查找,如果找到则返回最左边(最右边)和目标值相等的下标
* 如果没有找到则返回与目标值相比最左边(最右边)的下标
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchLeftIndexMost(int[] array, int target) {
// i和j都参与了比较运算
int i = 0;
int j = array.length - 1;
// 这里必须i<=j,因为当i=j时还需比较此时下标对应的值,即array[i]或array[j]
while (i <= j) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
// 如果是查找最左边重复的,则让j变小
if (target <= array[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
/
* 二分查找,如果找到则返回最左边(最右边)和目标值相等的下标
* 如果没有找到则返回与目标值相比最左边(最右边)的下标
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchRightIndexMost(int[] array, int target) {
// i和j都参与了比较运算
int i = 0;
int j = array.length - 1;
// 这里必须i<=j,因为当i=j时还需比较此时下标对应的值,即array[i]或array[j]
while (i <= j) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
if (target < array[m]) {
j = m - 1;
} else {
// 如果是查找最右边重复的,则让i变大
i = m + 1;
}
}
return i - 1;
}
/
* 二分查找,如果有重复值,则返回最左边(或最右边)的下标
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchLeftMost(int[] array, int target) {
// i和j都参与了比较运算
int i = 0;
int j = array.length - 1;
// 存储候选下标
int candidate = -1;
// 这里必须i<=j,因为当i=j时还需比较此时下标对应的值,即array[i]或array[j]
while (i <= j) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
if (target < array[m]) {
j = m - 1;
} else if (target > array[m]) {
i = m + 1;
} else {
// 赋值给候选者
candidate = m;
// 如果是查找最左边的,则让j变小
// j = m - 1;
// 如果是查找最右边的,则让i变大
i = m + 1;
}
}
return candidate;
}
/
* 测试二分查找
*/
private static void bs() {
int[] array = {5, 7, 9, 12, 23, 35, 56, 77, 123, 999, 1234};
int target = 888;
System.out.println(binarySearchAlternative(array, target));
/*
* java源码中的二分查找返回的是一个负数的插入点,即目标值在数组没找到时插入的位置下标
* 如果插入数组的下标为A, 则java源码返回的是 -(A+1).
* 为何+1呢? 因为查找时有可能A的值为0,如果直接返回-A即-0则和0没有区别,区分不出是否找到没有
* 因此要+1
*/
int index = Arrays.binarySearch(array, target);
System.out.println(index);
System.out.println("===========================");
// 使用插入点进行数组元素的插入
if (index < 0) {
// 关系式index = -(insertIndex+1)
int insertIndex = -(index + 1);
// 创建新数组,长度为原数组长度+1
int[] newArray = new int[array.length + 1];
// copy插入点之前的原数组值到新数组中
System.arraycopy(array, 0, newArray, 0, insertIndex);
// 把目标值插入到新数组中
newArray[insertIndex] = target;
// copy插入点之后的原数组值到新数组中
System.arraycopy(array, insertIndex, newArray, insertIndex + 1, array.length - insertIndex);
System.out.println(Arrays.toString(newArray));
}
}
/
* 二分查找
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchBasic(int[] array, int target) {
// i和j都参与了比较运算
int i = 0;
int j = array.length - 1;
// 这里必须i<=j,因为当i=j时还需比较此时下标对应的值,即array[i]或array[j]
while (i <= j) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
if (target < array[m]) {
j = m - 1;
} else if (target > array[m]) {
i = m + 1;
} else {
return m;
}
}
return -1;
}
/
* 二分查找改动版
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchAlternative(int[] array, int target) {
// i参与比较运算
int i = 0;
// 而j作为边界,不参与比较运算
int j = array.length;
// 这里必须i<j,如果是i<=j,则会在查找不存在的目标值时陷入死循环
while (i < j) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
if (target < array[m]) {
// 注意,此时下标m的值已经比较过了,因此j的边界值更新为m
j = m;
} else if (target > array[m]) {
// 而i还是要参与比较运算的,因此还是m+1
i = m + 1;
} else {
return m;
}
}
return -1;
}
/
* 二分查找平衡版,先找到下标再和目标值比较
* 优点: 减少了比较次数
* 缺点: 最坏(以前是logN)和最好(以前是常数)的时间复杂度都是logN
*
* @param array 被查找的数组
* @param target 目标值
* @return 找到返回下标, 找不到返回-1
*/
public static int binarySearchBalance(int[] array, int target) {
// i参与比较运算
int i = 0;
// 而j作为边界,不参与比较运算
int j = array.length;
// 判断j与i的距离是否大于1,如果小于等于1则表明快找到了
while (1 < j - i) {
// 如果写成(i + j) / 2会有int整型溢出造成负数的风险
int m = (i + j) >>> 1;
// 如果目标在左边,则更新j的值为m
if (target < array[m]) {
// j的边界值更新为m
j = m;
} else {
// 因为将大于和等于合并了,因此i值更新为m,此时m还未参加比较运算
// 在最后返回的时候在进行比较
i = m;
}
}
// 比较数组中下标i的值与目标是否相等
return array[i] == target ? i : -1;
}
}
递归
package com.lzlg.study.algorithm.new2023.recursion;
import java.util.Arrays;
/
* 递归案例-冒泡排序
*
* @author lzlg
* 2023/7/19 10:31
*/
public class BubbleSort {
public static void sort(int[] array) {
sort(array, array.length - 1);
}
/
* 递归方法,升序排序
*
* @param array 要排序的数组
* @param border 区分排序和未排序的边界下标
* 小于border的是未排序的,大于等于border的是已排序的
*/
private static void sort(int[] array, int border) {
// 如果边界已经为0了,则证明所有元素都已经有序了,递归终结
if (border == 0) {
return;
}
// 新的边界值
int newBorder = 0;
// 循环一遍后,边界之后的元素都是排好序的
for (int i = 0; i < border; i++) {
// 如果前面的比后面的大,则进行交换
if (array[i] > array[i + 1]) {
// 如果发生了交换,则下标i是新的边界border值
// 如果没有交换,则已经是有序了
int t = array[i];
array[i] = array[i + 1];
array[i + 1] = t;
// 将新的边界值赋值给newBorder
newBorder = i;
}
}
System.out.println("=======================");
System.out.println(Arrays.toString(array));
// 缩小边界
// sort(array, border - 1);
// newBorder是新的有序和无序的边界值
sort(array, newBorder);
}
public static void main(String[] args) {
int[] array = {3, 8, 1, 0, 4, 9, 10, 22, 16};
sort(array);
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归案例-阶乘
*
* @author lzlg
* 2023/7/19 9:52
*/
public class Factorial {
public static int f(int n) {
if (n < 0) {
throw new IllegalArgumentException("参数" + n + "不合法");
}
if (n == 0 || n == 1) {
return 1;
}
return n * f(n - 1);
}
public static void main(String[] args) {
int f = f(0);
System.out.println(f);
}
}
package com.lzlg.study.algorithm.new2023.recursion;
import java.util.Arrays;
/
* 递归案例-斐波那契数列-多路递归
*
* @author lzlg
* 2023/7/19 11:36
*/
public class Fibonacci {
/
* 递归次数公式f(n) = 2 * f(n+1) - 1
* 时间复杂度是1.618的n次幂
*/
public static int fibonacci(int n) {
if (n < 0) {
throw new IllegalArgumentException("参数n:" + n + "非法");
}
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
/
* 使用记忆法进行优化,优化后的时间复杂度为O(n),空间复杂度为O(n)
*/
public static int optimize(int n) {
// 使用数组长度为n+1的缓存,因为计算的斐波那契数列从0开始
int[] cache = new int[n + 1];
// 初始化数组中的值都为-1
Arrays.fill(cache, -1);
// 前两个斐波那契数列的值加入缓存中
cache[0] = 0;
cache[1] = 1;
return calc(n, cache);
}
private static int calc(int n, int[] cache) {
// 从缓存中取出已经计算过的
if (cache[n] != -1) {
return cache[n];
}
// 递归计算
int x = calc(n - 1, cache);
int y = calc(n - 2, cache);
// 将计算的结果缓存
cache[n] = x + y;
return cache[n];
}
public static void main(String[] args) {
System.out.println(fibonacci(9));
System.out.println("==================");
System.out.println(optimize(9));
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归案例-斐波那契数列数列-青蛙跳楼梯
* 楼梯有n阶
* 青蛙要跳到楼顶,可以一次跳一阶,也可以一次跳两阶
* 只能向上跳,问有多少种跳法?
*
* 楼阶 跳法
* 1 (1)
* 2 (1,1) (2)
* 3 (1,1,1) (2,1)
* (1,2)
* 4 (1,1,1,1) (1,2,1) (2,1,1)---最后一次跳为1-跳一阶
* (1,1,2) (2,2) ---最后一次跳为2-跳2阶
* 通过上述列表可观察出
* 当楼阶为4时,最后一次跳可分为1-跳一阶,2-跳2阶
* 当最后一次跳为1-跳一阶时,则前面的3阶楼梯的跳跃方法则对应楼阶为3的
* 当最后一次跳为2-跳2阶时,则前面的2阶楼梯的跳跃方法则对应楼阶为2的
* 如果楼阶为n的跳法为函数f(n),则有f(n) = f(n-1) + f(n-2)
* 对应楼阶为4,即f(4) = f(3) + f(2)
* @author lzlg
* 2023/7/19 11:59
*/
public class FrogJumpStairs {
}
package com.lzlg.study.algorithm.new2023.recursion;
import java.util.Deque;
import java.util.LinkedList;
/
* 递归-汉诺塔问题
*
* @author lzlg
* 2023/7/20 10:13
*/
public class HanoiTower {
static Deque<Integer> source = new LinkedList<>();
static Deque<Integer> helper = new LinkedList<>();
static Deque<Integer> target = new LinkedList<>();
/
* 汉诺塔移动
* 分析时间复杂度的公式:
* T(n) = 2T(n - 1) + c, T(1) = c;
*
* @param n 汉诺塔盘子数量
* @param source 存放原盘子的柱子
* @param helper 辅助移动盘子的柱子
* @param target 移动到的目标盘子的柱子
*/
private static void move(int n,
Deque<Integer> source,
Deque<Integer> helper,
Deque<Integer> target) {
// n为0,则不需要移动
if (n == 0) {
return;
}
// 可分解为
// 1.把前n-1个盘子移动到辅助柱子上
move(n - 1, source, target, helper);
// 2.把最底下的盘子移动到目标柱子上
target.addFirst(source.removeFirst());
// 打印
print();
// 3.把前n-1个盘子移动到目标柱子上
move(n - 1, helper, source, target);
}
private static void print() {
System.out.println("=======================");
System.out.println("源头柱子: " + source);
System.out.println("辅助柱子: " + helper);
System.out.println("目标柱子: " + target);
}
public static void main(String[] args) {
final int n = 3;
for (int i = 1; i <= n; i++) {
source.add(i);
}
// 打印
print();
move(n, source, helper, target);
}
}
package com.lzlg.study.algorithm.new2023.recursion;
import java.util.Arrays;
/
* 递归案例-插入排序
*
* @author lzlg
* 2023/7/19 10:57
*/
public class InsertionSort {
public static void sort(int[] array) {
insertion(array, 1);
// insertion2(array, 1);
}
/
* 插入排序,升序
*
* @param array 要排序的数组
* @param border 有序无序的边界值
* 大于等于border的是无序的,小于border的是有序的
*/
private static void insertion(int[] array, int border) {
// 如果边界值为数组的长度,则已经有序,结束递归
if (border == array.length) {
return;
}
// 保存边界下标对应的数组元素
int temp = array[border];
// 前面有序数组的下标,代表的是第一个小于temp的元素的下标
int i = border - 1;
// 依次遍历前面有序数组的元素,如果大于边界下标的元素值
// 则将有序数组的元素向后移动,空出插入位
// i>=0防止边界下标对应的元素在有序部分是最小的情况,防止数组越界
while (i >= 0 && array[i] > temp) {
array[i + 1] = array[i];
i--;
}
// 如果temp比数组中的元素都大,则while循环没有执行,也就不需要进行交换了
if ((i + 1) != border) {
// 找到了插入位置,进行插入
// 注意这里为i+1,因为找到的数组元素是小于temp的,因此temp应在i下标元素的后面
array[i + 1] = temp;
}
System.out.println("=======================");
System.out.println(Arrays.toString(array));
// 边界值增加
insertion(array, border + 1);
}
/
* 插入排序,升序,不使用临时变量temp
*
* @param array 要排序的数组
* @param border 有序无序的边界值
* 大于等于border的是无序的,小于border的是有序的
*/
private static void insertion2(int[] array, int border) {
// 如果边界值为数组的长度,则已经有序,结束递归
if (border == array.length) {
return;
}
// 有序数组的边界(最右边)
int i = border - 1;
// array[i + 1]是边界下标对应的数组元素,即要插入的元素
// 如果有序数组的前一个元素比后一个大,则进行交换
// 不过这种方法的交换次数较多,相比上面的实现效率较低,但时间复杂度一致
while (i >= 0 && array[i] > array[i + 1]) {
int t = array[i];
array[i] = array[i + 1];
array[i + 1] = t;
i--;
}
System.out.println("=======================");
System.out.println(Arrays.toString(array));
// 边界值增加
insertion2(array, border + 1);
}
/
* 只插入排序数组中的部分元素,区间为[left,right]
*
* @param array 待排序的数组
* @param left 左边界
* @param right 右边界
*/
public static void sortPart(int[] array, int left, int right) {
insertionPart(array, left, left + 1, right);
}
/
* 插入排序,升序,数组元素部分排序
*
* @param array 要排序的数组
* @param left 左边界
* @param border 有序无序的边界值
* 大于等于border的是无序的,小于border的是有序的
* @param right 右边界
*/
private static void insertionPart(int[] array, int left, int border, int right) {
// 如果边界值为右边界的长度+1,则已经有序,结束递归
if (border == right + 1) {
return;
}
// 保存边界下标对应的数组元素
int temp = array[border];
// 前面有序数组的下标,代表的是第一个小于temp的元素的下标
int i = border - 1;
// 依次遍历前面有序数组的元素,如果大于边界下标的元素值
// 则将有序数组的元素向后移动,空出插入位
// i>=left防止边界下标对应的元素在有序部分是最小的情况,防止数组越界
while (i >= left && array[i] > temp) {
array[i + 1] = array[i];
i--;
}
// 如果temp比数组中的元素都大,则while循环没有执行,也就不需要进行交换了
if ((i + 1) != border) {
// 找到了插入位置,进行插入
// 注意这里为i+1,因为找到的数组元素是小于temp的,因此temp应在i下标元素的后面
array[i + 1] = temp;
}
System.out.println("=======================");
System.out.println(Arrays.toString(array));
// 边界值增加
insertionPart(array, left, border + 1, right);
}
public static void main(String[] args) {
int[] array = {3, 8, 1, 0, 4, 9, 10, 22, 16};
// sort(array);
// 数组此部分8, 1, 0, 4, 9, 10有序
sortPart(array, 0, 8);
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归-杨辉三角
*
* @author lzlg
* 2023/7/20 10:47
*/
public class PascalTriangle {
/
* 跟行和列获取杨辉三角的元素值
* 杨辉三角有以下规律:
* 1.当列为1时, 元素值都为1
* 2.当行与列相等时, 元素值也都为1
* 3.i行j列的元素值= i-1行j-1列元素值 + i-1行j列元素值
*
* @param row 行数
* @param col 列数
* @return 杨辉三角的元素值
*/
public static int element(int row, int col) {
if (col == 1 || row == col) {
return 1;
}
return element(row - 1, col - 1) + element(row - 1, col);
}
/
* 打印杨辉三角
*
* @param row 行数
* @param space 元素之间的间距
*/
public static void print(int row, int space) {
for (int i = 1; i <= row; i++) {
// 打印每行的空格
spaceFormat(row, i, space);
for (int j = 1; j <= i; j++) {
System.out.printf("%-" + space + "d", element(i, j));
}
System.out.println();
}
}
/
* 输出每行的空格
*
* @param row 总行数
* @param i 当前行数
* @param space 空格幅度
*/
private static void spaceFormat(int row, int i, int space) {
int spaceCount = (row - i) * (space / 2);
for (int j = 0; j < spaceCount; j++) {
System.out.print(" ");
}
}
/
* 杨辉三角优化1:
* 使用二维数组记录每次运算的结果
*/
public static int fastElement(int[][] triangle, int row, int col) {
// 二维数组中如果存储了上次的计算结果,则直接返回
if (triangle[row][col] > 0) {
return triangle[row][col];
}
if (col == 1 || row == col) {
// 使用二维数组记录计算结果
triangle[row][col] = 1;
return 1;
}
// 使用二维数组记录计算结果
triangle[row][col] = fastElement(triangle, row - 1, col - 1) + fastElement(triangle, row - 1, col);
return triangle[row][col];
}
/
* 杨辉三角优化1:
* 打印杨辉三角
*
* @param row 行数
* @param space 元素之间的间距
*/
public static void fastPrint(int row, int space) {
// 使用二维数组记录杨辉三角的值,注意行数是row + 1,第一行不使用
int[][] triangle = new int[row + 1][];
for (int i = 1; i <= row; i++) {
// 初始化每行的数据,这里每行多了一列,第一列(下标为0)的不使用
triangle[i] = new int[i + 1];
// 打印每行的空格
spaceFormat(row, i, space);
for (int j = 1; j <= i; j++) {
System.out.printf("%-" + space + "d", fastElement(triangle, i, j));
}
System.out.println();
}
}
/
* 杨辉三角优化2:
* 使用一维数组记录运算结果,因为如果计算完本行的数据,上一行就不使用了
* 如果当前行是第一列,则只有一个1
* 下一行的每个元素是一维数组中当前元素的值加上前一个元素的值
* 第1行: 1 0 0 0 0
* 第2行: 1 1 0 0 0
* 第3行: 1 2 1 0 0
* 第4行: 1 3 3 1 0
*
* @param rowElements 一维数组
* @param i 当前行数
*/
public static void calcRowElement(int[] rowElements, int i) {
if (i == 1) {
rowElements[i] = 1;
return;
}
// 下一行的每个元素是一维数组中当前元素的值加上前一个元素的值
for (int j = i; j > 1; j--) {
rowElements[j] = rowElements[j] + rowElements[j - 1];
}
}
/
* 杨辉三角优化2:
* 打印杨辉三角
*
* @param row 行数
* @param space 元素之间的间距
*/
public static void rushPrint(int row, int space) {
// 使用一维数组记录杨辉三角的值,注意行数是row + 1,第一个不使用
int[] rowElements = new int[row + 1];
for (int i = 1; i <= row; i++) {
// 生成杨辉三角的元素值存储在一维数组中
calcRowElement(rowElements, i);
// 打印每行的空格
spaceFormat(row, i, space);
for (int j = 1; j <= i; j++) {
System.out.printf("%-" + space + "d", rowElements[j]);
}
System.out.println();
}
}
public static void main(String[] args) {
rushPrint(8, 6);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 有环的链表
* 如下的链表
* 1 -> 2 -> 3 -> 4 -> 5 -> 3
*
* @author lzlg
* 2023/7/21 15:09
*/
public class CycleLinkedList {
/
* 检测链表是否有环路,使用弗洛伊德龟兔赛跑法
* 兔子指针走两步,乌龟指针走一步
* 如果链表有环路,则兔子一定能够再次追上乌龟
*
* @param node 链表
*/
public static boolean hasCycle(ListNode node) {
// 兔子指针
ListNode r = node;
// 乌龟指针
ListNode t = node;
while (r != null && r.next != null) {
r = r.next.next;
t = t.next;
// 再次相遇,则一定有环
if (t == r) {
return true;
}
}
// 兔子到达终点,则没有环
return false;
}
/
* 找到环路入口
* 步骤:
* 1.从第一次相遇开始,乌龟回到起点(head节点),兔子保持不动
* 2.然后乌龟和兔子开始循环,并且都走一步
* 3.当再次相遇的时候,此时的节点就是环的入口
* 原理:
* 设起点到环入口的距离为a, 环的长度为b
* 那么从起点开始, [走 a + 绕环n圈, 都能找到环入口], 即走 a + n*b
* [第一次相遇]的时候: (注意是相遇的时候,此时如果有环,则一定在环上相遇)
* 假如兔子走了 a + x*b + k圈 (x是兔子绕环的圈数, k是不在环入口的步数)
* 乌龟走了 a + y*b + k圈 (y是乌龟绕环的圈数, k是不在环入口的步数)
* 兔子走的距离是乌龟的两倍(因兔子走两步,乌龟走一步),因此有
* 乌龟走的 = (a + x*b + k) - (a + y*b + k) = (x - y)*b 为绕环(x-y)圈
* 因此此时乌龟走了 (x - y)*b 步
* 而兔子是乌龟的两倍, 则是 2*(x - y)*b 步
* 如果此时,让兔子留着原地,乌龟回到起点,并都按一步的步数走
* 当再走a步(a的值未知)的时候,此时乌龟走了a + (x - y)*b步数
* 而兔子走了a + 2*(x - y)*b步数
* 因有规则: [走 a + 绕环n圈, 都能找到环入口]
* 所以兔子和乌龟一定在环入口相遇
*
* @param head 链表
*/
public static ListNode findCycleEntry(ListNode head) {
// 兔子指针
ListNode h = head;
// 乌龟指针
ListNode t = head;
while (h != null && h.next != null) {
// 乌龟走一步
t = t.next;
// 兔子走两步
h = h.next.next;
// 第一次相遇,则一定有环
if (h == t) {
// 乌龟回到起点
t = head;
// 此时都开始一步步走
while (true) {
// 如果再次相遇则一定是环入口
// 当链表首尾相接时,第一次相遇时,就已经在环的入口了,因此将t==h的判断提前
if (t == h) {
return t;
}
// 兔子和乌龟都走一步
t = t.next;
h = h.next;
}
}
}
// 兔子到达终点,则没有环,则没有环入口
return null;
}
public static void main(String[] args) {
// 创建链表
ListNode node = ListNode.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
ListNode p12 = findNode(node, 12);
ListNode p8 = findNode(node, 8);
ListNode p1 = findNode(node, 1);
// 构造环路
p12.next = p1;
// System.out.println(node);
// System.out.println("检测链表是否有环: " + hasCycle(node));
ListNode entry = findCycleEntry(node);
System.out.println("链表的环入口: " + entry.val);
}
/
* 找到和目标值相等的节点
*
* @param node 链表
* @param target 目标值
* @return 节点
*/
private static ListNode findNode(ListNode node, int target) {
ListNode p = node;
while (p != null && p.val != target) {
p = p.next;
}
return p;
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 删除链表中指定值的节点
*
* @author lzlg
* 2023/7/20 14:55
*/
public class DeleteLinkListValue {
/
* 方法1: 双指针
* 从链表中删除给定值的节点
* 使用两个指针
* 使用一个哨兵节点,防止删除操作的一些判空代码
* 第一个指针指向待删除节点的上一个节点
* 第二个指针指向待删除节点
*
* @param node 链表头节点
* @param target 目标值
*/
private static ListNode removeValue(ListNode node, int target) {
ListNode sentinel = new ListNode(-1, node);
ListNode p1 = sentinel;
ListNode p2 = p1.next;
while (p2 != null) {
// 如果找到,则进行删除
if (p2.val == target) {
// 把前节点p1的next指向p2的下一个节点
p1.next = p2.next;
// 移动p2指针
p2 = p2.next;
} else {// 没有找到,则p1,p2指针向后移动
p1 = p1.next;
p2 = p2.next;
}
}
return sentinel.next;
}
/
* 方法1的简化版
* 从链表中删除给定值的节点
* 使用两个指针
* 使用一个哨兵节点,防止删除操作的一些判空代码
* 第一个指针指向待删除节点的上一个节点
* 第二个指针指向待删除节点
*
* @param node 链表头节点
* @param target 目标值
*/
private static ListNode fastRemoveValue(ListNode node, int target) {
ListNode sentinel = new ListNode(-1, node);
ListNode p1 = sentinel;
ListNode p2;
// 把原先最后的p2 = p1.next;语句和上面的ListNode p2 = p1.next;合并到while循环里
while ((p2 = p1.next) != null) {
// 如果找到,则进行删除
if (p2.val == target) {
// 把前节点p1的next指向p2的下一个节点
p1.next = p2.next;
// 经过上述步骤后,p1的下个节点也是p2
// p2 = p1.next;
} else {// 没有找到,则p1,p2指针向后移动
p1 = p1.next;
// 经过上步p1的指针移动后,p1的下个节点也是p2
// p2 = p1.next;
}
// p2 = p1.next;
}
return sentinel.next;
}
/
* 方法2: 使用递归
* 有两种情况
* 1.如果当前递归过程中节点的值等于目标值
* 则我不返回自己,返回节点的next节点
* 2.如果当前递归过程中节点的值不等于目标值
* 则我返回自己,但有可能当前节点以后的节点有等于目标值的节点
* 因此要更新当前节点的next
*
* @param node 链表头节点
* @param target 目标值
*/
public static ListNode recursionRemove(ListNode node, int target) {
if (node == null) {
return null;
}
if (node.val == target) {
return recursionRemove(node.next, target);
} else {
node.next = recursionRemove(node.next, target);
return node;
}
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 2, 3, 4, 4, 6);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("=======删除后========");
ListNode node = recursionRemove(first, 4);
System.out.println(node);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 找到链表中间节点
* [1, 2, 3, 4, 5]中间节点为3
* [1, 2, 3, 4, 5, 6] 中间节点为4(取右边的)
*
* @author lzlg
* 2023/7/21 13:37
*/
public class FindMiddleNode {
/
* 使用快慢指针, 第1个指针走一步,第2个指针走两步
* 当第二个指针指向null或第二个指针的next为null时,停止循环,此时第一个指针指向的是中间节点
*
* @param node 链表
* @return 中间节点
*/
public static ListNode findMiddle(ListNode node) {
ListNode p1 = node;
ListNode p2 = node;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next;
p2 = p2.next;
}
return p1;
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 2, 3, 4, 5);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("======中间节点=======");
ListNode middle = findMiddle(first);
System.out.println(middle);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* @author lzlg
* 2023/7/20 11:33
*/
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
/
* 创建不定元素的链表
*
* @param members 元素
* @return 链表
*/
public static ListNode of(int... members) {
if (members == null || members.length == 0) {
return null;
}
ListNode head = null;
for (int i = members.length - 1; i >= 0; i--) {
head = new ListNode(members[i], head);
}
return head;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
ListNode p = this;
while (p != null) {
sb.append(p.val);
if (p.next != null) {
sb.append(", ");
}
p = p.next;
}
sb.append("]");
return sb.toString();
}
// public static void main(String[] args) {
// ListNode third = new ListNode(3);
// ListNode second = new ListNode(2, third);
// ListNode first = new ListNode(1, second);
// System.out.println(first);
// }
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
import java.util.Arrays;
/
* 合并有序数组
*
* @author lzlg
* 2023/7/21 16:21
*/
public class MergeTwoSortedArray {
/
* 非递归实现
*
* @param a1 原数组
* @param i 前有序的起点下标
* @param iEnd 前有序的终点下标
* @param j 后有序的起点下标
* @param jEnd 后有序的终点下标
* @param a2 合并后的数组
*/
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
// 访问数组a2的下标
int k = 0;
while (i <= iEnd && j <= jEnd) {
// 谁小把谁放入a2数组
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
// 前有序部分没有元素,但后一部分可能还有
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}
/
* 递归实现
*
* @param a1 原数组
* @param i 前有序的起点下标
* @param iEnd 前有序的终点下标
* @param j 后有序的起点下标
* @param jEnd 后有序的终点下标
* @param a2 合并后的数组
* @param k 数组a2的下标
*/
public static void mergeRecursion(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2, int k) {
// 如果前半部分没有了,则添加下半部分到a2
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
return;
}
// 如果后半部分没有了,则添加上半部分到a2
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
return;
}
// 如果i下标的元素小于j的
if (a1[i] < a1[j]) {
a2[k] = a1[i];
// 进行递归调用
mergeRecursion(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
} else {
a2[k] = a1[j];
mergeRecursion(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
}
}
public static void main(String[] args) {
// 注意数组的前一部分和后一部分都是有序的
int[] a1 = {1, 3, 5, 6, 8, 2, 4, 7, 9, 10};
int[] a2 = new int[a1.length];
// merge(a1, 0, 4, 5, 9, a2);
mergeRecursion(a1, 0, 4, 5, 9, a2, 0);
System.out.println(Arrays.toString(a2));
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 合并两个有序链表
* [1, 3]
* [2, 4, 5]
* 合并为
* [1, 2, 3, 4, 5]
*
* @author lzlg
* 2023/7/21 11:40
*/
public class MergeTwoSortedLinkedList {
/
* 方法1: 使用三个指针
* 第一个指针是新链表(有哨兵节点)的指针p
* 第2和3指针分别是两个链表的指针p1和p2
* <p>
* 循环时, 比较p1和p2当前value值的大小,将小的加入到p的next,然后同时移动小的链表指针和指针p
* 直到p1和p2有一个为null时退出循环,然后将不为null的链表的剩余节点都添加到新链表p中
*
* @param p1 链表1
* @param p2 链表2
* @return 合并后的新链表
*/
public static ListNode merge(ListNode p1, ListNode p2) {
ListNode sentinel = new ListNode(-1, null);
ListNode p = sentinel;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 == null) {
p.next = p2;
}
if (p2 == null) {
p.next = p1;
}
return sentinel.next;
}
/
* 方法2: 使用递归
* 每次递归返回一个较小的节点
* 为了将递归的节点串联起来,因此需要把返回的节点的next指向下次递归的结果
*
* @param p1 链表1
* @param p2 链表2
* @return 合并后的新链表
*/
public static ListNode mergeRecursion(ListNode p1, ListNode p2) {
// 递归终结条件:直到p1或p2为null
if (p1 == null) {
return p2;
}
if (p2 == null) {
return p1;
}
// 如果p1值小,则使用p1的next继续递归
if (p1.val < p2.val) {
// 使用p1.next将递归返回的最小值串联起来
p1.next = mergeRecursion(p1.next, p2);
return p1;
} else {
p2.next = mergeRecursion(p1, p2.next);
return p2;
}
}
/
* 合并多个有序的链表
* 使用分治算法,将数组从中间分割两部分,直到只有一个数组元素为止
* 如果只有一个数组元素,则直接返回这个数组元素对应的链表
* 然后会有左边的一个链表和右边一个链表,进行两个链表的合并(上面的方法)
*
* @param nodes 有序链表数组
* @return 新链表
*/
public static ListNode mergeMultiple(ListNode[] nodes) {
if (nodes == null || nodes.length == 0) {
return null;
}
return mergeMultipleRecursion(nodes, 0, nodes.length - 1);
}
/
* 递归合并多个有序链表的方法
*
* @param nodes 有序链表数组
* @param left 左边界下标
* @param right 右边界下标
* @return 新链表
*/
private static ListNode mergeMultipleRecursion(ListNode[] nodes, int left, int right) {
// 如果左边界下标=右边界下标,则当前边界内只有一个链表,直接取出
if (left == right) {
return nodes[left];
}
// 从中间切分为左右两份
int mid = (left + right) >>> 1;
// 向左递归切分数组
ListNode leftNode = mergeMultipleRecursion(nodes, left, mid);
// 向右递归切分数组
ListNode rightNode = mergeMultipleRecursion(nodes, mid + 1, right);
// 合并两个链表
return mergeRecursion(leftNode, rightNode);
}
public static void main(String[] args) {
ListNode fifth = new ListNode(5, null);
ListNode forth = new ListNode(4, fifth);
ListNode second = new ListNode(2, forth);
ListNode third = new ListNode(3, null);
ListNode first = new ListNode(1, third);
ListNode node2 = new ListNode(8, null);
ListNode node1 = new ListNode(0, node2);
System.out.println("======原始链表1=======");
System.out.println(first);
System.out.println("======原始链表2=======");
System.out.println(second);
// System.out.println("======两个链表合并后=======");
// ListNode node = mergeRecursion(first, second);
// System.out.println(node);
System.out.println("多个链表进行合并===========");
ListNode node = mergeMultiple(new ListNode[]{first, second, node1});
System.out.println(node);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 判断是不是回文链表
* 1->2->1 是
* 1->2->3 不是
*
* @author lzlg
* 2023/7/21 14:04
*/
public class PalindromeLinked {
/
* 判断链表是不是回文链表
* 分为三个步骤
* 1.找到中间节点链表,将链表拆分为两个链表了
* [1, 2, 2, 1] -> [1, 2] 和 [2, 1]
* 2.反转慢指针下的链表,将[2, 1]反转为[1, 2]
* 3.逐一比较前面的链表和反转后的链表的value值
*
* @param node 链表
* @return 结果
*/
public static boolean isPalindrome(ListNode node) {
// 找到中间节点链表
ListNode middle = middle(node);
// 反转中间节点链表
// 新链表的头部
ListNode newNode = null;
while (middle != null) {
// 保留原链表的下一个节点
ListNode next = middle.next;
// 插入到新链表的头部
middle.next = newNode;
// 新链表的指针回到头部
newNode = middle;
// 跳到下一个节点,继续循环
middle = next;
}
ListNode reversed = newNode;
// 逐一比较两个链表元素
while (reversed != null) {
// 如果有一个不相等,直接返回false
if (reversed.val != node.val) {
return false;
}
reversed = reversed.next;
node = node.next;
}
// 如果全部相等,则是回文,返回true
return true;
}
/
* 找到链表中间节点
*/
private static ListNode middle(ListNode node) {
ListNode p1 = node;
ListNode p2 = node;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 2, 3, 4, 3, 2, 1);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("======是回文吗?=======");
System.out.println(fastIsPalindrome(first));
}
/
* 判断链表是不是回文链表
* 分为二个步骤,将上面的1,2步骤合并了
* 1.找到中间节点链表,再遍历过程中,反转前面的节点
* [1, 2, 2, 1] -> [1, 2] 和 [2, 1] 反转前面的节点 [2, 1] 和 [2, 1]
* 2.逐一比较前面反转的链表和后面的链表的value值
*
* @param node 链表
* @return 结果
*/
public static boolean fastIsPalindrome(ListNode node) {
// 在查找中间节点过程中,反转前面的链表
ListNode p1 = node;
ListNode p2 = node;
// 新链表的头部
ListNode newNode = null;
ListNode old = node;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
// 保留原链表的下一个节点,此时next相当于p1
// ListNode next = old.next;
// 插入到新链表的头部
old.next = newNode;
// 新链表的指针回到头部
newNode = old;
// 跳到下一个节点,继续循环
// old = next;
old = p1;
}
// 如果是奇数个节点,则循环退出后,p1指向的是中间节点
// 但前面的节点(不管反转了没有)没有此中间节点,因此需要让p1再走一步
// 如何判断是奇数个节点呢?那就是p2不为空时
if (p2 != null) {
p1 = p1.next;
}
System.out.println(p1);
System.out.println(newNode);
// 逐一比较两个链表元素
while (newNode != null) {
// 如果有一个不相等,直接返回false
if (newNode.val != p1.val) {
return false;
}
newNode = newNode.next;
p1 = p1.next;
}
// 如果全部相等,则是回文,返回true
return true;
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 删除链表倒数第n个节点
*
* @author lzlg
* 2023/7/20 15:34
*/
public class RemoveNthNumber {
/
* 方法1: 递归
* 删除倒数第n个节点
* 递归方法返回一个计数,从最底部计数
* 当计数等于n的时候,就删除当前递归的节点
*
* @param node 链表头节点
* @param n 倒数第n个
* @return 链表
*/
private static ListNode removeNthNumber(ListNode node, int n) {
// 哨兵节点,用于辅助删除链表中倒数最后一个(即第一个)
ListNode sentinel = new ListNode(-1, node);
removeNode(sentinel, n);
return sentinel.next;
}
/
* 递归删除链表节点
* 节点: 1 -> 2 -> 3 -> 4 -> 5 -> null
* 倒数计数: 5 4 3 2 1 0
* 如果没有哨兵节点,则删除链表中倒数最后一个时(如上是值为1的倒数第5个的节点)
* 则因为没有前一个节点,故删除不了
*
* @param node 链表节点
* @param n 倒数第n个
* @return 计数
*/
private static int removeNode(ListNode node, int n) {
// 遇到节点为null,则返回0
if (node == null) {
return 0;
}
// 后面节点的计数值
int nth = removeNode(node.next, n);
// 如果计数相等,则进行节点删除
if (nth == n) {
// 当前节点的next指向下一个节点的下一个节点
// 就把下个节点(计数值等于n的节点)删除了
node.next = node.next.next;
}
// 则当前节点是后面节点的计数值+1
return nth + 1;
}
/
* 方法1: 双指针
* 步骤:
* 1.开始时,两个指针都指向哨兵节点
* 2.根据传入的倒数n值, 将第二个指针向后移动n+1步
* 为何是n+1步? 因为单链表删除元素要找到待删除节点的上个节点
* 3.然后开始循环,两个指针都同步移动
* 直到第二个指针指向null,则第一个指针就是待删除节点的上个节点
* 4.进行删除
*
* @param node 链表头节点
* @param n 倒数第n个
* @return 链表
*/
private static ListNode loopRemoveNthNumber(ListNode node, int n) {
if (n <= 0) {
return node;
}
// 哨兵节点,用于辅助删除链表中倒数最后一个(即第一个)
ListNode sentinel = new ListNode(-1, node);
// p1是待删除节点的前节点
ListNode p1 = sentinel;
// p2用于辅助找到待删除节点
ListNode p2 = sentinel;
// p2指针移动n+1步
for (int i = 0; i < n + 1; i++) {
// 如果p2为null,则表示已经超过链表长度,直接返回原链表
if (p2 == null) {
return sentinel.next;
}
p2 = p2.next;
}
// p1和p2同步移动
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
// while循环后,p1指向待删除节点的前一个节点
// 进行删除
p1.next = p1.next.next;
return sentinel.next;
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 2, 3, 4, 5, 6);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("=======删除后========");
ListNode node = loopRemoveNthNumber(first, 0);
System.out.println(node);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 反转链表
*
* @author lzlg
* 2023/7/20 11:41
*/
public class ReverseList {
/
* 方法1: 使用新的链表,遍历旧链表,把旧链表的元素插入到新链表的头部
*
* @param old 旧链表
* @return 反转后的新链表
*/
private static ListNode reverse1(ListNode old) {
// 新链表
ListNode newNode = null;
// 遍历指针
ListNode p = old;
while (p != null) {
// 插入到新链表的头部
newNode = new ListNode(p.val, newNode);
p = p.next;
}
return newNode;
}
/
* 方法2: 使用新的链表,遍历旧链表
* 把旧链表的元素删除后(这样不用创建新的节点)插入到新链表的头部
*
* @param old 旧链表
* @return 反转后的新链表
*/
private static ListNode reverse2(ListNode old) {
// 旧链表
List oldList = new List(old);
// 新链表
List newList = new List(null);
while (true) {
ListNode first = oldList.removeFirst();
if (first == null) {
break;
}
newList.addFirst(first);
}
return newList.head;
}
/
* 辅助方法2的List
*/
static class List {
ListNode head;
public List(ListNode head) {
this.head = head;
}
/
* 添加新节点到头部
*
* @param first 新节点
*/
public void addFirst(ListNode first) {
// 将删除的头节点的下个节点指向新链表的头节点
first.next = head;
// 移动新链表的头指针到新节点上
head = first;
}
/
* 移出头部节点
*
* @return 头部节点
*/
public ListNode removeFirst() {
// 保存头部节点指针
ListNode first = head;
if (first != null) {
head = first.next;
}
return first;
}
}
/
* 方法3: 使用递归
* 先找到最后一个节点,将此节点的next指向它的上一个节点
* 为防止循环引用,将它的上一个节点的next指向null
* 1 -> 2 -> 3 -> 4 -> 5
* 找到最后一个节点5,将5的next指向4
* 1 -> 2 -> 3 -> 4 -> 5 -> 4
* 为防止循环引用,将节点4的next指向null
* 1 -> 2 -> 3 -> 4 -> null 5 -> 4
*
* @param node 旧链表
* @return 反转后的新链表
*/
private static ListNode reverse3(ListNode node) {
// 递归终结条件,找到最后一个节点,因为最后一个节点的next指向null
if (node == null || node.next == null) {
return node;
}
ListNode last = reverse3(node.next);
// 此时node是前一个节点,是描述里的节点4
// 而node.next是节点5
node.next.next = node;
node.next = null;
return last;
}
/
* 方法4: 使用三个指针:
* 一个是新链表的头指针(始终指向头部)
* 一个是旧链表头部指针(始终指向头部)
* 一个是旧链表的头部指针的next指针,即要移动的节点
* 每次循环都把next指针移动到链表的头部,如下:
* n是新链表头指针,o是旧链表头指针,s是要移动的节点
* 开始时:
* n/o s
* 1 -> 2 -> 3 -> 4 -> 5 -> null
* 第一次循环:
* n/o s 变成 2 -> 3 -> 4 -> 5 -> null
* 1 -> 3 -> 4 -> 5 -> null 对应 node.next = second.next;
* s n/o
* 2 -> 1 -> 3 -> 4 -> 5 -> null 对应 second.next = newNode;
* s/n o
* 2 -> 1 -> 3 -> 4 -> 5 -> null 对应 newNode = second;
* n o s
* 2 -> 1 -> 3 -> 4 -> 5 -> null 对应 second = node.next;
*
* @param node 旧链表
* @return 反转后的新链表
*/
private static ListNode reverse(ListNode node) {
// 如果链表为空,或只有一个节点,直接返回
if (node == null || node.next == null) {
return node;
}
// 新链表的头指针(始终指向头部),默认是旧链表的头一个节点
ListNode newNode = node;
// 旧链表的第二个节点
ListNode second = node.next;
// 循环条件: 直到没有下一个节点可移动
while (second != null) {
// 将旧链表的头指针指向第二个节点的next
node.next = second.next;
// 将第二个节点的next指向新节点
second.next = newNode;
// 移动新链表的头指针为第二个节点(因newNode要始终指向头部)
newNode = second;
// 把旧链表的下一个节点给second,继续循环
second = node.next;
}
return newNode;
}
/
* 方法5: 思路和方法2一样,不过是面向过程的
*
* @param node 旧链表
* @return 反转后的新链表
*/
private static ListNode reverse5(ListNode node) {
// 如果链表为空,或只有一个节点,直接返回
if (node == null || node.next == null) {
return node;
}
// 新链表头节点,始终指向头节点
ListNode newNode = null;
while (node != null) {
// 将下一个节点保留
ListNode next = node.next;
// 将next插入到新链表的头部
// 相当于断开了与旧链表的关系,插入了新链表的头部
node.next = newNode;
// 将newNode指向新链表的头节点,因为newNode始终指向头节点
newNode = node;
// 将旧节点指向保留的下一个节点
node = next;
}
return newNode;
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 2, 3, 4, 5);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("=======反转后========");
ListNode newNode = reverse(first);
System.out.println(newNode);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 有序链表进行去重,但保留
* [1, 1, 2, 3, 3]
* 去重后
* [1, 2, 3]
*
* @author lzlg
* 2023/7/21 10:51
*/
public class SortLinkedRemoveDuplicates {
/
* 方法1: 使用双指针
* 开始时,第一个指针p1指向链表头节点,第二个指针p2指向头节点的next
* 开始循环,情况有:
* 1.检测到p1的value等于p2的value时,将p2删除
* 2.p1的value和p2的value不相等时,p1和p2同步移动
*
* @param node 链表头节点
* @return 新链表头节点
*/
public static ListNode removeDuplicates(ListNode node) {
// 当链表为空,或只有一个节点时直接返回
if (node == null || node.next == null) {
return node;
}
ListNode p1 = node;
ListNode p2;
// p2在下次循环前也会移动
while ((p2 = p1.next) != null) {
// 如果相等,则删除p2
if (p1.val == p2.val) {
p1.next = p2.next;
} else {
// 不相等,则移动,p2的移动转移到while循环条件上了
p1 = p1.next;
}
}
return node;
}
/
* 方法2: 使用递归
* 如果递归过程中,有以下情况
* 1.当前节点遇到和当前节点下个节点的value值相等时,则直接返回下个节点,相当于删除当前节点
* 2.如果不想等,则还是返回自身,但当前节点的后面节点还会有重复的,因此要更新当前节点的next
*
* @param node 链表头节点
* @return 新链表头节点
*/
public static ListNode removeDuplicatesRecursion(ListNode node) {
// 当链表为空,或只有一个节点时直接返回
if (node == null || node.next == null) {
return node;
}
if (node.val == node.next.val) {
return removeDuplicatesRecursion(node.next);
} else {
node.next = removeDuplicatesRecursion(node.next);
return node;
}
}
public static void main(String[] args) {
ListNode first = ListNode.of(1, 1, 2, 3, 3);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("=======去重后========");
ListNode newNode = removeDuplicatesRecursion(first);
System.out.println(newNode);
}
}
package com.lzlg.study.algorithm.new2023.recursion.quiz;
/
* 有序链表进行去重,不保留
* [1, 1, 2, 3, 3]
* 去重后
* [2]
*
* @author lzlg
* 2023/7/21 10:51
*/
public class SortLinkedRemoveDuplicatesNoKeep {
/
* 方法1: 使用三指针
* 这里使用哨兵节点s
* <p>
* 开始时:
* 第一个指针p1指向哨兵节点s
* 第2个指针p2指向哨兵节点s的next
* 第3个指针p3指向哨兵节点s的next的next
* <p>
* 开始循环:
* 1.当p2的value和p3的value相等时,需要再次循环p3直到找到和p2不等的节点,然后将p1指向此节点
* 2.当p2的value和p3的value不相等时,则三个指针同步移动
*
* @param node 链表头节点
* @return 新链表头节点
*/
public static ListNode removeDuplicates(ListNode node) {
// 当链表为空,或只有一个节点时直接返回
if (node == null || node.next == null) {
return node;
}
ListNode sentinel = new ListNode(-1, node);
ListNode p1 = sentinel;
ListNode p2, p3;
// p2,p3在下次循环前跟着p1移动
while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
// 如果p2和p3相等
if (p2.val == p3.val) {
// 使用循环移动p3,直到找到和p2的value不同的节点
while ((p3 = p3.next) != null && p3.val == p2.val) ;
// 循环后,p3指向的是不同p2的value的节点
// 将p1的next指向p3,因为不保留重复元素,因此这个操作把所有重复元素都删除了
p1.next = p3;
} else {
// 不相等,则移动,p2和p3的移动转移到while循环条件上了
p1 = p1.next;
}
}
return sentinel.next;
}
/
* 方法2: 使用递归
* 情况有:
* 1.当前节点遇到和当前节点的value相等的next节点时,就一直循环,直到找到和当前节点value不同的节点,再递归此节点
* 2.当不相等时,返回当前节点,当前节点的后面的节点可能会有重复,因此更新当前节点的next
*
* @param node 链表头节点
* @return 新链表头节点
*/
public static ListNode removeDuplicatesRecursion(ListNode node) {
// 当链表为空,或只有一个节点时直接返回
if (node == null || node.next == null) {
return node;
}
// 当前节点的value和下个节点value相等时
if (node.val == node.next.val) {
// 找到不同于当前节点value的节点
ListNode temp = node.next.next;
while (temp != null && temp.val == node.val) {
temp = temp.next;
}
// 然后递归此节点,当前节点和当前节点的next都不要了
return removeDuplicatesRecursion(temp);
} else {
node.next = removeDuplicatesRecursion(node.next);
return node;
}
}
public static void main(String[] args) {
ListNode fifth = new ListNode(4, null);
ListNode forth = new ListNode(3, fifth);
ListNode third = new ListNode(1, forth);
ListNode second = new ListNode(1, third);
ListNode first = ListNode.of(1, 1, 1, 3, 4);
System.out.println("======原始链表=======");
System.out.println(first);
System.out.println("=======去重删除元素后========");
ListNode newNode = removeDuplicatesRecursion(first);
System.out.println(newNode);
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归案例-斐波那契数列-兔子问题
* 第一个月, 有一对成熟的兔子
* 第二个月, 它们成熟
* 第三个月, 它们能产下一对新的小兔子
* 所有兔子遵循相同规律, 求第n个月的兔子数
*
* @author lzlg
* 2023/7/19 11:45
*/
public class RabbitQuestion {
public static void main(String[] args) {
// 解决思路, 假设第n个月的兔子数量函数f为f(n)
// 如果是第6个月
// 则第6个月的兔子数是第5个月所有的兔子数 + 第4个月的兔子产下的未成熟的兔子数
// 第5个月所有的兔子数为f(5)
// 因为第4个月的兔子在第6个月的时候已经成熟了
// 第4个月的兔子数量和第6月中未成熟的兔子数相等,即f(4)
// 因此可得f(6) = f(5) + f(4)
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归案例-二分查找
*
* @author lzlg
* 2023/7/19 10:10
*/
public class RecursionBinarySearch {
public static int binarySearch(int[] array, int target) {
return find(array, target, 0, array.length - 1);
}
private static int find(int[] array, int target, int left, int right) {
// 递归终结条件,如果左边下标大于右边的下标,则没有找到返回-1
if (left > right) {
return -1;
}
// 中间值下标
int m = (left + right) >>> 1;
// 大于中间值,向右查找
if (target > array[m]) {
return find(array, target, m + 1, right);
}
// 小于中间值,向左查找
if (target < array[m]) {
return find(array, target, left, m - 1);
}
// 如果相等就是m
return m;
}
public static void main(String[] args) {
int[] array = {2, 5, 8, 9, 14, 22, 31, 44};
System.out.println(binarySearch(array, 2));
System.out.println(binarySearch(array, 5));
System.out.println(binarySearch(array, 8));
System.out.println(binarySearch(array, 9));
System.out.println(binarySearch(array, 14));
System.out.println(binarySearch(array, 22));
System.out.println(binarySearch(array, 31));
System.out.println(binarySearch(array, 44));
System.out.println(binarySearch(array, 3));
System.out.println(binarySearch(array, 16));
System.out.println(binarySearch(array, 55));
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 递归案例-反向打印字符串
*
* @author lzlg
* 2023/7/19 9:59
*/
public class ReversePrintString {
public static void print(String str) {
// print0(0, str);
print1(str.length() - 1, str);
}
private static void print0(int n, String str) {
// 当n增加到字符串的长度时,不再递归
if (n == str.length()) {
return;
}
// 先递到最里层,也就是到字符串的最后一个字符上
print0(n + 1, str);
// 打印字符
System.out.println(str.charAt(n));
}
private static void print1(int n, String str) {
// 当n增加到字符串的长度时,不再递归
if (n == -1) {
return;
}
// 先打印字符,因为是从n是从最大变换到最小的
System.out.println(str.charAt(n));
// 递到最里层,也就是到字符串的第一个字符上
print1(n - 1, str);
}
public static void main(String[] args) {
print("12345");
}
}
package com.lzlg.study.algorithm.new2023.recursion;
/
* 尾部递归
*
* @author lzlg
* 2023/7/19 14:49
*/
public class TailRecursion {
public static void main(String[] args) {
// java运行此代码,会出现StackOverflowError
// 而scala语言,则会优化为平行调用
System.out.println(sum(100_000, 0));
}
public static int sum(int n, int sum) {
if (n == 1) {
return 1 + sum;
}
return sum(n - 1, sum + n);
}
/
* 尾部递归,最后必须是return一个方法
* 有些语言如Scala可对尾部递归优化成平行的调用
*/
public static int sum(int n) {
return sum1(n + 1);
}
public static int sum1(int n) {
return sum2(n + 1);
}
public static int sum2(int n) {
return 2;
}
}
树
package com.lzlg.study.algorithm.new2023.tree.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
import com.lzlg.study.algorithm.new2023.tree.TreeTraversal;
import java.util.Arrays;
/
* 1.根据前中序遍历构建二叉树
* 2.根据中后序遍历构建二叉树
*
* @author lzlg
* 2023/7/27 11:42
*/
public class LoopBuildTree {
/
* 根据前中序遍历构建二叉树
*
* @param prevOrder 前序遍历数组
* @param midOrder 中序遍历数组
* @return 二叉树
*/
public TreeNode buildTreeByPrevAndMid(int[] prevOrder, int[] midOrder) {
// 当前序遍历数组为null(或中序遍历数组为null)时返回null
if (prevOrder.length == 0) {
return null;
}
// 前序遍历数组中的第一个值是根节点的值
int rootValue = prevOrder[0];
// 创建根节点
TreeNode root = new TreeNode(rootValue);
// 遍历中序遍历数组,区分左子树和右子树
for (int i = 0; i < midOrder.length; i++) {
// 在中序遍历数组找到和根节点值一样的下标
if (midOrder[i] == rootValue) {
// 把中序遍历数组分成左子树和右子树,Arrays.copyOfRange()方法范围不包括右边
int[] midLeft = Arrays.copyOfRange(midOrder, 0, i);
int[] midRight = Arrays.copyOfRange(midOrder, i + 1, midOrder.length);
// 同样的,把前序遍历数组分成左子树和右子树
int[] prevLeft = Arrays.copyOfRange(prevOrder, 1, i + 1);
int[] prevRight = Arrays.copyOfRange(prevOrder, i + 1, prevOrder.length);
// 然后开始递归
// 左子树
root.left = buildTreeByPrevAndMid(prevLeft, midLeft);
// 右子树
root.right = buildTreeByPrevAndMid(prevRight, midRight);
break;
}
}
// 返回根节点-结果
return root;
}
/
* 根据中后序遍历构建二叉树
*
* @param midOrder 中序遍历数组
* @param nextOrder 后序遍历数组
* @return 二叉树
*/
public TreeNode buildTreeByMidAndNext(int[] midOrder, int[] nextOrder) {
// 当中序遍历数组为null(或后序遍历数组为null)时返回null
if (midOrder.length == 0) {
return null;
}
// 后序遍历的最后一个节点是根节点
int rootValue = nextOrder[nextOrder.length - 1];
// 创建根节点
TreeNode root = new TreeNode(rootValue);
// 遍历中序遍历数组
for (int i = 0; i < midOrder.length; i++) {
// 如果找到根节点,则开始切分
if (midOrder[i] == rootValue) {
// 把中序遍历数组分成左子树和右子树,Arrays.copyOfRange()方法范围不包括右边
int[] midLeft = Arrays.copyOfRange(midOrder, 0, i);
int[] midRight = Arrays.copyOfRange(midOrder, i + 1, midOrder.length);
// 同样的,把后序遍历数组分成左子树和右子树
int[] nextLeft = Arrays.copyOfRange(nextOrder, 0, i);
int[] nextRight = Arrays.copyOfRange(nextOrder, i, nextOrder.length - 1);
// 然后开始递归
// 左子树
root.left = buildTreeByMidAndNext(midLeft, nextLeft);
// 右子树
root.right = buildTreeByMidAndNext(midRight, nextRight);
break;
}
}
return root;
}
public static void main(String[] args) {
// 前序遍历结果数组
int[] prevOrder = {1, 2, 4, 3, 6, 7};
// 中序遍历结果数组
int[] midOrder = {4, 2, 1, 6, 3, 7};
// 后序遍历结果数组
int[] nextOrder = {4, 2, 6, 7, 3, 1};
// 遍历二叉树
TreeTraversal loop = new TreeTraversal(System.out::println);
// 构建二叉树
LoopBuildTree tree = new LoopBuildTree();
// 根据前中序遍历构建二叉树
// TreeNode node = tree.buildTreeByPrevAndMid(prevOrder, midOrder);
// 根据中后序遍历构建二叉树
TreeNode node = tree.buildTreeByMidAndNext(midOrder, nextOrder);
// 使用前序遍历,中序遍历,后序遍历检查结果
System.out.println("=====前序=====");
loop.prevOrder(node);
System.out.println("=====中序=====");
loop.middleOrder(node);
System.out.println("=====后序=====");
loop.nextOrder(node);
}
}
package com.lzlg.study.algorithm.new2023.tree.quiz;
import java.util.LinkedList;
/
* 后缀表达式转化为二叉树
* 使用一个栈
* 1.遇到数值组装成树节点后直接入栈
* 2.遇到运算符(根),则弹出栈中两个节点(先弹出的是右节点),组合后再入栈
*
* @author lzlg
* 2023/7/27 11:01
*/
public class SuffixExpressionToTree {
/
* 后缀表达式转化为二叉树
*
* @param tokens 后缀表达式数组
* @return 二叉树根节点
*/
public TreeNode suffixExpressionToTree(String[] tokens) {
// 使用栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 遍历数组
for (String str : tokens) {
switch (str) {
// 遇到运算符
case "+":
case "-":
case "*":
case "/":
// 弹出栈两个元素,注意第一个弹出的是左节点
TreeNode right = stack.pop();
TreeNode left = stack.pop();
// 当前元素是父节点
TreeNode parent = new TreeNode(str);
// 设置父节点的左右子节点
parent.left = left;
parent.right = right;
// 将父节点入栈
stack.push(parent);
break;
default:
// 遇到数字,封装为树节点,直接入栈
stack.push(new TreeNode(str));
}
}
// 最后的栈的栈顶元素是根节点
return stack.peek();
}
/
* 节点类
*/
static class TreeNode {
private String value;
private TreeNode left;
private TreeNode right;
public TreeNode(String value) {
this.value = value;
}
public TreeNode(String value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
/
* 后序遍历树节点
*
* @param node 节点
*/
public void nextOrder(TreeNode node) {
if (node == null) {
return;
}
nextOrder(node.left);
nextOrder(node.right);
System.out.println(node.value);
}
public static void main(String[] args) {
String[] tokens = {"2", "1", "-", "3", "*"};
SuffixExpressionToTree tree = new SuffixExpressionToTree();
TreeNode root = tree.suffixExpressionToTree(tokens);
tree.nextOrder(root);
}
}
package com.lzlg.study.algorithm.new2023.tree.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
/
* 判断是否是对称二叉树
* 对称的:
* 1
* / \
* 2 2
* /\ /\
* 3 4 4 3
* 非对称:
* 1
* / \
* 2 2
* /\ /\
* 3 4 3 4
*
* @author lzlg
* 2023/7/26 16:01
*/
public class SymmetricTree {
/
* 检查是否是对称二叉树
*
* @param node 树根节点
* @return 结果
*/
public static boolean symmetric(TreeNode node) {
return checkSymmetric(node.left, node.right);
}
/
* 检查左右子节点是否对称
*
* @param left 左子节点
* @param right 右子节点
* @return 结果
*/
private static boolean checkSymmetric(TreeNode left, TreeNode right) {
// 只有一个节点,一定对称
if (left == null && right == null) {
return true;
}
// 如果有一个子节点为空,一个不为空,则必不对称
if (left == null || right == null) {
return false;
}
// 如果左右子节点的值不相等,则必不对称
if (left.value != right.value) {
return false;
}
// 检查左节点的左子节点和右节点的右子节点是否对称
// 检查左节点的右子节点和右节点的左子节点是否对称
return checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
}
public static void main(String[] args) {
// 不对称的
TreeNode node1 = new TreeNode(
new TreeNode(new TreeNode(3), 2, new TreeNode(4)),
1,
new TreeNode(new TreeNode(3), 2, new TreeNode(4))
);
System.out.println(symmetric(node1));
System.out.println("=====================");
// 对称的
TreeNode node2 = new TreeNode(
new TreeNode(new TreeNode(3), 2, new TreeNode(4)),
1,
new TreeNode(new TreeNode(4), 2, new TreeNode(3))
);
System.out.println(symmetric(node2));
}
}
package com.lzlg.study.algorithm.new2023.tree.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/
* 求二叉树最大深度
*
* @author lzlg
* 2023/7/27 10:00
*/
public class TreeMaxDepth {
/
* 使用递归实现
*
* @param node 树根节点
* @return 树最大深度
*/
public static int maxDepthRecursion(TreeNode node) {
// 如果当前节点为null,则深度为0
if (node == null) {
return 0;
}
// 求节点的左子树的最大深度
int leftDepth = maxDepthRecursion(node.left);
// 求节点的右子树的最大深度
int rightDepth = maxDepthRecursion(node.right);
// 选出其中最大深度+当前深度1即是二叉树的最大深度
return Integer.max(leftDepth, rightDepth) + 1;
}
/
* 使用后序遍历实现,栈在遍历过程中的size最大值就是树的最大栈深度
*
* @param node 树根节点
* @return 树最大深度
*/
public static int maxDepthNextOrder(TreeNode node) {
// 使用栈进行后序遍历
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode p = node;
// 记录最近一次弹出栈的元素
TreeNode pop = null;
int depth = 0;
// 进行循环
while (p != null || !stack.isEmpty()) {
if (p != null) {
// 如果当前节点不为null则压栈,为了记录回来的路
stack.push(p);
// 如果栈中元素数量大于上次存储的栈深度,则赋值给depth
if (stack.size() > depth) {
depth = stack.size();
}
p = p.left;
} else {
// 如果节点遍历完成,从栈中查看栈顶元素
TreeNode peek = stack.peek();
// 如果栈顶元素的右节点为null,或右节点为最近弹出的节点
// 则证明左右节点已访问完成
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
} else {// 如果有右子节点,则赋值给p指针,下次循环访问
p = peek.right;
}
}
}
return depth;
}
/
* 使用层序遍历实现
*
* @param node 树根节点
* @return 树最大深度
*/
public static int maxDepthLevel(TreeNode node) {
// 如果当前节点为null,则深度为0
if (node == null) {
return 0;
}
TreeNode p = node;
// 使用队列进行层序遍历
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
// 深度
int depth = 0;
while (!queue.isEmpty()) {
// 当前层次的节点数量
int size = queue.size();
// 进行该层次的遍历
for (int i = 0; i < size; i++) {
// 弹出队列元素
TreeNode poll = queue.poll();
// 添加下一层的节点,即当前队列(存储的是上一层节点)弹出元素的左右子节点
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
// 遍历完成,层次深度+1
depth++;
}
return depth;
}
public static void main(String[] args) {
TreeNode node = new TreeNode(
new TreeNode(new TreeNode(3), 2, new TreeNode(4)),
1,
new TreeNode(new TreeNode(4), 2, new TreeNode(new TreeNode(5), 3, new TreeNode(6)))
);
System.out.println("递归实现,树的最大深度为: " + maxDepthRecursion(node));
System.out.println("后序遍历实现,树的最大深度为: " + maxDepthNextOrder(node));
System.out.println("层序遍历实现,树的最大深度为: " + maxDepthLevel(node));
System.out.println("==================================");
node = new TreeNode(
new TreeNode(null, 2, null),
1,
null
);
System.out.println("递归实现,树的最大深度为: " + maxDepthRecursion(node));
System.out.println("后序遍历实现,树的最大深度为: " + maxDepthNextOrder(node));
System.out.println("层序遍历实现,树的最大深度为: " + maxDepthLevel(node));
}
}
package com.lzlg.study.algorithm.new2023.tree.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/
* 求二叉树最小深度
*
* @author lzlg
* 2023/7/27 10:31
*/
public class TreeMinDepth {
/
* 使用递归实现
*
* @param node 节点
* @return 最小深度
*/
public static int minDepthRecursion(TreeNode node) {
if (node == null) {
return 0;
}
// 左子树最小深度
int leftDepth = minDepthRecursion(node.left);
// 右子树最小深度
int rightDepth = minDepthRecursion(node.right);
// 当左子树为null时,应该取右子树的最小深度
if (leftDepth == 0) {
return rightDepth + 1;
}
// 同样的当右子树为null时,应该取左子树的最小深度
if (rightDepth == 0) {
return leftDepth + 1;
}
return Integer.min(leftDepth, rightDepth) + 1;
}
/
* 使用层序遍历实现
* 当层序遍历遇到第一个叶子节点时候,此时叶子节点的所在深度就是最小深度
*
* @param node 节点
* @return 最小深度
*/
public static int minDepthLevel(TreeNode node) {
// 如果当前节点为null,则深度为0
if (node == null) {
return 0;
}
TreeNode p = node;
// 使用队列进行层序遍历
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
// 深度
int depth = 0;
while (!queue.isEmpty()) {
// 当前层次的节点数量
int size = queue.size();
// 进行该层次的遍历
for (int i = 0; i < size; i++) {
// 弹出队列元素
TreeNode poll = queue.poll();
// 遇到叶子节点,直接返回深度
if (poll.left == null && poll.right == null) {
return depth + 1;
}
// 添加下一层的节点,即当前队列(存储的是上一层节点)弹出元素的左右子节点
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
// 遍历完成,层次深度+1
depth++;
}
return depth;
}
public static void main(String[] args) {
TreeNode node = new TreeNode(
new TreeNode(new TreeNode(3), 2, new TreeNode(4)),
1,
new TreeNode(new TreeNode(4), 2, new TreeNode(new TreeNode(5), 3, new TreeNode(6)))
);
System.out.println("递归实现,树的最小深度为: " + minDepthRecursion(node));
System.out.println("层序遍历实现,树的最小深度为: " + minDepthLevel(node));
System.out.println("==================================");
node = new TreeNode(
new TreeNode(null, 2, null),
1,
null
);
System.out.println("递归实现,树的最小深度为: " + minDepthRecursion(node));
System.out.println("层序遍历实现,树的最小深度为: " + minDepthLevel(node));
}
}
package com.lzlg.study.algorithm.new2023.tree.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
/
* 翻转二叉树
*
* @author lzlg
* 2023/7/27 10:43
*/
public class TreeReversal {
/
* 翻转二叉树
*
* @param root 二叉树根节点
* @return 翻转后的二叉树
*/
public TreeNode reversal(TreeNode root) {
reversalBy(root);
return root;
}
/
* 翻转的递归方法
*
* @param node 节点
*/
public void reversalBy(TreeNode node) {
if (node == null) {
return;
}
// 进行翻转
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// 递归左右子树进行翻转
reversalBy(node.left);
reversalBy(node.right);
}
}
package com.lzlg.study.algorithm.new2023.tree;
import java.util.LinkedList;
import java.util.function.IntConsumer;
/
* 使用循环进行树的遍历
* 需要使用到数据结构栈
* 1.前序遍历,先访问节点,然后再访问左右节点
* 2.中序遍历,先访问左节点,然后访问当前节点,最后访问右节点
* 3.后续遍历,先访问左右节点,然后再访问当前节点
*
* @author lzlg
* 2023/7/26 11:36
*/
public class TreeLoopTraversal {
// 访问节点方式
private final IntConsumer consumer;
public TreeLoopTraversal(IntConsumer consumer) {
this.consumer = consumer;
}
/
* 前序遍历,先访问当前节点
*
* @param node 树节点
*/
public void prevOrder(TreeNode node) {
// 创建栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 访问节点指针
TreeNode p = node;
// 循环条件: 节点指针不为null或栈不为空时
while (p != null || !stack.isEmpty()) {
if (p != null) {
// 前序遍历直接访问当前节点
consumer.accept(p.value);
// 把当前节点压栈,为了记住回来的路
stack.push(p);
// 然后跳转到左子节点
p = p.left;
} else {
// 从栈中弹出元素,开始回溯
TreeNode pop = stack.pop();
// 开始访问节点右节点
p = pop.right;
}
}
}
/
* 中序遍历,先访问左子节点
*
* @param node 树节点
*/
public void middleOrder(TreeNode node) {
// 创建栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 访问节点指针
TreeNode p = node;
// 循环条件: 节点指针不为null或栈不为空时
while (p != null || !stack.isEmpty()) {
if (p != null) {
// 把当前节点压栈,为了记住回来的路
stack.push(p);
// 然后跳转到左子节点
p = p.left;
} else {
// 从栈中弹出元素,开始回溯
TreeNode pop = stack.pop();
// 中序遍历,此时左子树的访问已经完成(存储到栈中),访问从栈中弹出的左子节点
consumer.accept(pop.value);
// 开始访问节点右节点
p = pop.right;
}
}
}
/
* 后序遍历,先访问左右子节点
*
* @param node 树节点
*/
public void nextOrder(TreeNode node) {
// 创建栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 访问节点指针
TreeNode p = node;
// 最近一次弹出栈元素
TreeNode pop = null;
// 循环条件: 节点指针不为null或栈不为空时
while (p != null || !stack.isEmpty()) {
if (p != null) {
// 把当前节点压栈,为了记住回来的路
stack.push(p);
// 然后跳转到左子节点
p = p.left;
} else {
// 查看堆顶元素
TreeNode peek = stack.peek();
// 判断右子树是否处理完成,两种情况
// 1.如果是叶子节点,则叶子节点的right指针为null,则右子树处理完成
// 2.如果是非叶子节点,则叶子节点的right指向最近一次弹出栈元素,则右子树处理完成
if (peek.right == null || peek.right == pop) {
// 从栈中弹出元素,开始回溯
pop = stack.pop();
// 后序遍历,此时左子树的访问已经完成(存储到栈中),访问从栈中弹出的左子节点
consumer.accept(pop.value);
} else {// 右子树没有处理完成,则进行处理右子树
// 开始访问节点右节点
p = peek.right;
}
}
}
}
/
* 统一的遍历方式
*
* @param node 树节点
*/
public void loopOrder(TreeNode node) {
// 创建栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 访问节点指针
TreeNode p = node;
// 最近一次弹出栈元素
TreeNode pop = null;
// 循环条件: 节点指针不为null或栈不为空时
while (p != null || !stack.isEmpty()) {
if (p != null) {
// 把当前节点压栈,为了记住回来的路
stack.push(p);
// 前序遍历
System.out.println("前序: " + p.value);
// 然后跳转到左子节点
p = p.left;
} else {
// 查看堆顶元素
TreeNode peek = stack.peek();
// 判断右子树是否处理完成,两种情况
// 1.如果是叶子节点,则叶子节点的right指针为null,则右子树处理完成
if (peek.right == null) {
// 中序遍历,如果没有右子树,则需打印当前弹出元素的值
System.out.println("中序: " + peek.value);
// 从栈中弹出元素,开始回溯
pop = stack.pop();
// 后序遍历
System.out.println("后序: " + pop.value);
// 2.如果是非叶子节点,则叶子节点的right指向最近一次弹出栈元素,则右子树处理完成
} else if (peek.right == pop) {
// 从栈中弹出元素,开始回溯
pop = stack.pop();
// 后序遍历
System.out.println("后序: " + pop.value);
} else {// 右子树没有处理完成,则进行处理右子树
// 中序遍历
System.out.println("中序: " + peek.value);
// 开始访问节点右节点
p = peek.right;
}
}
}
}
public static void main(String[] args) {
TreeLoopTraversal test = new TreeLoopTraversal(System.out::println);
TreeNode node = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
// System.out.println("前序遍历:");
// test.prevOrder(node);
// System.out.println("中序遍历:");
// test.middleOrder(node);
// System.out.println("后序遍历:");
// test.nextOrder(node);
test.loopOrder(node);
}
}
package com.lzlg.study.algorithm.new2023.tree;
/
* 树节点
*
* @author lzlg
* 2023/7/26 11:34
*/
public class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) {
this.value = value;
}
public TreeNode(TreeNode left, int value, TreeNode right) {
this.left = left;
this.value = value;
this.right = right;
}
}
package com.lzlg.study.algorithm.new2023.tree;
import java.util.function.IntConsumer;
/
* 树的遍历
* 1.前序遍历,先访问节点,然后再访问左右节点
* 2.中序遍历,先访问左节点,然后访问当前节点,最后访问右节点
* 3.后续遍历,先访问左右节点,然后再访问当前节点
*
* @author lzlg
* 2023/7/26 11:36
*/
public class TreeTraversal {
// 访问节点方式
private final IntConsumer consumer;
public TreeTraversal(IntConsumer consumer) {
this.consumer = consumer;
}
/
* 前序遍历
*
* @param node 树节点
*/
public void prevOrder(TreeNode node) {
if (node == null) {
return;
}
consumer.accept(node.value);
prevOrder(node.left);
prevOrder(node.right);
}
/
* 中序遍历
*
* @param node 树节点
*/
public void middleOrder(TreeNode node) {
if (node == null) {
return;
}
middleOrder(node.left);
consumer.accept(node.value);
middleOrder(node.right);
}
/
* 后序遍历
*
* @param node 树节点
*/
public void nextOrder(TreeNode node) {
if (node == null) {
return;
}
nextOrder(node.left);
nextOrder(node.right);
consumer.accept(node.value);
}
public static void main(String[] args) {
TreeTraversal test = new TreeTraversal(System.out::println);
TreeNode node = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
System.out.println("前序遍历:");
test.prevOrder(node);
System.out.println("中序遍历:");
test.middleOrder(node);
System.out.println("后序遍历:");
test.nextOrder(node);
}
}
二叉搜索树
package com.lzlg.study.algorithm.new2023.bts;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;
/
* 二叉搜索树Binary Search Tree
* 左子节点的key都小于父节点
* 右子节点的key都大于父节点
*
* @author lzlg
* 2023/7/28 9:46
*/
public class BinarySearchTree {
// 根节点
private BSTNode root;
/
* 二叉搜索树节点
*/
static class BSTNode {
// 关键字,不能重复,用于标识节点
int key;
// 节点存储的元素值
Object value;
// 左子节点
BSTNode left;
// 右子节点
BSTNode right;
public BSTNode(int key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
/
* 根据关键字获取值
*
* @param key 关键字
* @return 元素值
*/
public Object get(int key) {
return recursionGet(root, key);
}
/
* 递归根据关键字获取值
*
* @param node 节点
* @param key 关键字
* @return 元素值
*/
private Object recursionGet(BSTNode node, int key) {
// 如果节点为null,则找到头了,直接返回null
if (node == null) {
return null;
}
// 小于,则从左找
if (key < node.key) {
return recursionGet(node.left, key);
} else if (key > node.key) {// 大于,则从右找
return recursionGet(node.right, key);
} else {// 找到,直接返回
return node.value;
}
}
/
* 使用循环根据关键字获取值
*
* @param key 关键字
* @return 元素值
*/
private Object loopGet(int key) {
// 指针
BSTNode p = root;
// 循环
while (p != null) {
// 小于,向左找
if (key < p.key) {
p = p.left;
// 大于,向右找
} else if (key > p.key) {
p = p.right;
} else {
// 找到,则返回
return p.value;
}
}
// 循环退出则是没找到
return null;
}
/
* 获取二叉搜索树key最大的元素值
*
* @return 元素值
*/
public Object getMax() {
// 树是空的,直接返回null
if (root == null) {
return null;
}
// 一直向右查找
BSTNode p = root;
// 找到没有右子树的节点,则是key最大
while (p.right != null) {
p = p.right;
}
return p.value;
}
/
* 找到二叉树的key最大的节点的元素值
*
* @param node 节点
* @return 元素值
*/
private Object max(BSTNode node) {
// 树是空的,直接返回null
if (node == null) {
return null;
}
// 一直向右查找
BSTNode p = node;
// 找到没有右子树的节点,则是key最大
while (p.right != null) {
p = p.right;
}
return p.value;
}
/
* 获取二叉搜索树key最小的元素值
*
* @return 元素值
*/
public Object getMin() {
// 树是空的,直接返回null
if (root == null) {
return null;
}
// 一直向左查找
BSTNode p = root;
// 找到没有左子树的节点,则是key最小
while (p.left != null) {
p = p.left;
}
return p.value;
}
/
* 获取二叉搜索树key最小的元素值
*
* @param node 节点
* @return 元素值
*/
private Object min(BSTNode node) {
// 树是空的,直接返回null
if (node == null) {
return null;
}
// 一直向左查找
BSTNode p = node;
// 找到没有左子树的节点,则是key最小
while (p.left != null) {
p = p.left;
}
return p.value;
}
/
* 向二叉搜索树放入元素,有两种情况
* 1.如果找到key相等的,则进行替换
* 2.如果没找到,则进行添加
*
* @param key 关键字
* @param value 元素值
*/
public void put(int key, Object value) {
// 如果树为空,则直接添加
if (root == null) {
root = new BSTNode(key, value);
return;
}
// 指针
BSTNode p = root;
// 待插入位置的父节点
BSTNode parent = null;
// 进行循环
while (p != null) {
// 记录父节点
parent = p;
// 小于,向左找
if (key < p.key) {
p = p.left;
// 大于,向右找
} else if (key > p.key) {
p = p.right;
} else {
// 找到,则进行替换,然后返回
p.value = value;
return;
}
}
// 没找到,则进行插入
// 需要找到待插入位置的父节点
// 如果小于,则插入父节点的左边
if (key < parent.key) {
parent.left = new BSTNode(key, value);
} else { // 如果大于,则插入父节点的右边
parent.right = new BSTNode(key, value);
}
// 没有等于情况,如果等于,则在循环里就找到了
}
/
* 找到key的前驱节点的元素值
* 1.先找到key对应的节点
* 2.如果此节点有左子树,则前驱节点是左子树中的key最大的
* 3.如果此节点无左子树,则前驱节点是从左来的最近的祖先节点
*
* @param key 关键字
* @return 前驱节点的元素值
*/
public Object former(int key) {
if (root == null) {
return null;
}
// 当前节点的指针
BSTNode p = root;
// 祖先节点
BSTNode ancestor = null;
// 进行循环
while (p != null) {
// 小于,向左找
if (key < p.key) {
p = p.left;
// 大于,向右找
} else if (key > p.key) {
// 记录最近的,从左来的祖先节点
ancestor = p;
p = p.right;
} else {
// 找到退出循环
break;
}
}
// 如果没找到,则直接返回
if (p == null) {
return null;
}
// 情况1:如果有左子树,则找到左子树中key最大的
if (p.left != null) {
return max(p.left);
}
// 情况2:如果没有左子树,则是从左来的,最近的祖先节点的元素值
// 如果没有,则是没有前驱节点,返回null
return ancestor == null ? null : ancestor.value;
}
/
* 找到key的后驱节点的元素值
* 1.先找到key对应的节点
* 2.如果此节点有右子树,则后驱节点是右子树中的key最小的
* 3.如果此节点无右子树,则后驱节点是从右来的最近的祖先节点
*
* @param key 关键字
* @return 前驱节点的元素值
*/
public Object latter(int key) {
// 如果树为空,直接返回null
if (root == null) {
return null;
}
// 当前节点
BSTNode p = root;
// 记录祖先节点
BSTNode ancestor = null;
// 循环找到key对应的节点
while (p != null) {
// 小于,向左找
if (key < p.key) {
// 记录最近的,从右来的节点
ancestor = p;
p = p.left;
// 大于,向右找
} else if (key > p.key) {
p = p.right;
} else {
// 找到,则跳出循环
break;
}
}
// 没找到当前节点,则直接返回null
if (p == null) {
return null;
}
// 情况1:节点有右子树,则取右子树中key最小的元素值
if (p.right != null) {
return min(p.right);
}
// 情况2:节点没有右子树,则取最近的从右来的祖先节点的元素值
// 如果没有这样的祖先节点,则返回null
return ancestor == null ? null : ancestor.value;
}
/
* 删除key对应的节点,并返回节点的元素值
* 有四种情况:
* 1.如果待删除节点只有左子树,则把父节点的左指针指向待删除节点的左子树
* 2.如果待删除节点只有右子树,则把父节点的右指针指向待删除节点的右子树
* 3.如果待删除节点没有左右子树,则直接删除(该情况可包含在情况1,2中)
* 4.如果待删除节点有左右子树,先找到待删除节点的[后继节点](也可以是前继节点)
* 1)如果后继节点是待删除节点的右子树(不相邻),则直接用该后继节点替换待删除节点
* 同时更新后继节点的左指针指向待删除节点的左指针
* 2)如果后继节点和待删除节点不相邻,则先处理把后继节点的右子树赋给该后继节点的父节点
* 然后用后继节点替换待删除节点,并更新后继节点的左右子节点指针分别指向待删除节点的左右指针
*
* @param key 待删除的节点key
* @return 待删除的节点的元素值
*/
public Object delete(int key) {
// 如果树为空,直接返回null
if (root == null) {
return null;
}
// 找到待删除节点
BSTNode p = root;
// 待删除节点的父节点
BSTNode parent = null;
while (p != null) {
// 小于,向左找
if (key < p.key) {
parent = p;
p = p.left;
// 大于,向右找
} else if (key > p.key) {
parent = p;
p = p.right;
} else {
// 找到,退出循环
break;
}
}
// 如果没有找到,直接返回null
if (p == null) {
return null;
}
// 情况1:只有右子树
if (p.left == null) {
shift(parent, p, p.right);
// 情况2:只有左子树
} else if (p.right == null) {
shift(parent, p, p.left);
// 情况4:有左右子树
} else {
// 找到后继节点(可参考方法latter的代码)
BSTNode latter = p.right;
// 由于要处理后继节点,需要记录后继节点的父节点
// 刚开始,后继节点的父节点是待删除节点p
BSTNode latterParent = p;
// 找到后继节点(后继节点一定没有左子树)
while (latter.left != null) {
// 更新后继节点的父节点
latterParent = latter;
latter = latter.left;
}
// 情况2)如果后继节点的父节点不是待删除节点,则先删除后继节点
if (latterParent != p) {
// 先删除后继节点(后继节点一定没有左子树),然后再删除待删除节点
shift(latterParent, latter, latter.right);
// 要更新后继节点的右子树,即是待删除节点的右子树
latter.right = p.right;
}
// 情况1)如果后继节点的父节点就是待删除节点,则进行替换
// 删除待删除节点
shift(parent, p, latter);
// 注意,要更新后继节点的左指针,因为shift方法只更新了单个的左或右指针
latter.left = p.left;
}
// 返回删除节点的元素值
return p.value;
}
/
* 进行变更
* 1.如果没有父节点(根节点删除的情况),则直接把替换的节点赋值给root
* 2.如果待删除节点是父节点的左节点,则把父节点的左节点指向替换节点
* 3.如果待删除节点是父节点的右节点,则把父节点的右节点指向替换节点
*
* @param parent 父节点
* @param deleted 待删除节点
* @param replaced 替换节点
*/
private void shift(BSTNode parent, BSTNode deleted, BSTNode replaced) {
if (parent == null) {
root = replaced;
} else if (parent.left == deleted) {
parent.left = replaced;
} else {
parent.right = replaced;
}
}
/
* 使用递归方法删除
*
* @param key 关键字
* @return 删除节点的元素值
*/
public Object recursionDelete(int key) {
List<Object> list = new ArrayList<>(1);
// 删除节点后的树root需调整
root = recursionDelete(root, key, list);
return list.isEmpty() ? null : list.get(0);
}
/
* 使用递归方法删除
*
* @param node 当前节点
* @param key 关键字
* @return 删除节点的元素值
*/
private BSTNode recursionDelete(BSTNode node, int key, List<Object> result) {
// 如果当前节点为null,直接返回null
if (node == null) {
return null;
}
// 如果key小于当前节点的key,则向左递归查找
if (key < node.key) {
// 在递归过程中可能会删除节点,需要将返回的节点保留
node.left = recursionDelete(node.left, key, result);
return node;
}
// 如果key大于当前节点的key,则向右递归查找
if (key > node.key) {
// 在递归过程中可能会删除节点,需要将返回的节点保留
node.right = recursionDelete(node.right, key, result);
return node;
}
// 记录待删除节点的值
result.add(node.value);
// 找到待删除节点,即当前节点node
// 情况1:待删除节点只有右子树
if (node.left == null) {
return node.right;
}
// 情况2:待删除节点只有左子树
if (node.right == null) {
return node.left;
}
// 情况3:同时有左右子树,则查找当前节点(待删除节点)的后继节点
BSTNode latter = node.right;
// 开始查找后继节点
while (latter.left != null) {
latter = latter.left;
}
// 递归调用,先删除后继节点,注意key变成后继节点的key了
// 待删除节点的右子树删除后继节点后,因为要用后继节点代替待删除节点
// 因此后继节点的右子树即是处理过的待删除节点的右子树
latter.right = recursionDelete(node.right, latter.key, new ArrayList<>());
// 后继节点的左子树是待删除节点的左子树
latter.left = node.left;
// 返回后继节点
return latter;
}
/
* 查找比key小的节点的元素值集合,使用中序遍历
* 因为中序遍历二叉搜索树的结果是有序的
*
* @param key 关键字
* @return 元素值集合
*/
public List<Object> less(int key) {
List<Object> result = new ArrayList<>();
if (root == null) {
return result;
}
// 使用栈
LinkedList<BSTNode> stack = new LinkedList<>();
BSTNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理
if (pop.key < key) {
result.add(pop.value);
} else {
break;
}
p = pop.right;
}
}
return result;
}
/
* 查找比key大的节点的元素值集合,使用中序遍历
* 因为中序遍历二叉搜索树的结果是有序的
*
* @param key 关键字
* @return 元素值集合
*/
public List<Object> greater(int key) {
List<Object> result = new ArrayList<>();
if (root == null) {
return result;
}
// 使用栈
LinkedList<BSTNode> stack = new LinkedList<>();
BSTNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
/
* 查找在两个key之间的节点的元素值集合,使用中序遍历
* 因为中序遍历二叉搜索树的结果是有序的
*
* @param minKey 最小关键字
* @param maxKey 最大关键字
* @return 元素值集合
*/
public List<Object> between(int minKey, int maxKey) {
List<Object> result = new ArrayList<>();
if (root == null) {
return result;
}
// 使用栈
LinkedList<BSTNode> stack = new LinkedList<>();
BSTNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理
if (pop.key >= minKey && pop.key <= maxKey) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
/
* 打印二叉搜索树
*
* @param consumer 打印方式
*/
public void print(Consumer<BSTNode> consumer) {
middleOrder(root, consumer);
}
/
* 中序遍历打印
*
* @param node 节点
* @param consumer 输出方式
*/
private void middleOrder(BSTNode node, Consumer<BSTNode> consumer) {
if (node == null) {
return;
}
middleOrder(node.left, consumer);
consumer.accept(node);
middleOrder(node.right, consumer);
}
}
package com.lzlg.study.algorithm.new2023.bts;
/
* 二叉搜索树-泛型
*
* @author lzlg
* 2023/7/28 9:46
*/
public class GenericBinarySearchTree<K extends Comparable<K>, V> {
// 根节点
private BSTNode<K, V> root;
/
* 二叉搜索树节点
*/
static class BSTNode<K, V> {
// 关键字,不能重复,用于标识节点
K key;
// 节点存储的元素值
V value;
// 左子节点
BSTNode<K, V> left;
// 右子节点
BSTNode<K, V> right;
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
/
* 根据关键字获取值
*
* @param key 关键字
* @return 元素值
*/
public V get(K key) {
return recursionGet(root, key);
}
/
* 递归根据关键字获取值
*
* @param node 节点
* @param key 关键字
* @return 元素值
*/
private V recursionGet(BSTNode<K, V> node, K key) {
// 如果节点为null,则找到头了,直接返回null
if (node == null) {
return null;
}
// 进行比较,-1则key比node.key小,0相等,1则key比node.key大
int compare = key.compareTo(node.key);
// 小于,则从左找
if (compare < 0) {
return recursionGet(node.left, key);
} else if (compare > 0) {// 大于,则从右找
return recursionGet(node.right, key);
} else {// 找到,直接返回
return node.value;
}
}
/
* 使用循环根据关键字获取值
*
* @param key 关键字
* @return 元素值
*/
private V loopGet(K key) {
// 指针
BSTNode<K, V> p = root;
// 循环
while (p != null) {
// 进行比较,-1则key比node.key小,0相等,1则key比node.key大
int compare = key.compareTo(p.key);
// 小于,向左找
if (compare < 0) {
p = p.left;
// 大于,向右找
} else if (compare > 0) {
p = p.right;
} else {
// 找到,则返回
return p.value;
}
}
// 循环退出则是没找到
return null;
}
/
* 获取二叉搜索树key最大的元素值
*
* @return 元素值
*/
public V getMax() {
// 树是空的,直接返回null
if (root == null) {
return null;
}
// 一直向右查找
BSTNode<K, V> p = root;
// 找到没有右子树的节点,则是key最大
while (p.right != null) {
p = p.right;
}
return p.value;
}
/
* 获取二叉搜索树key最小的元素值
*
* @return 元素值
*/
public V getMin() {
// 树是空的,直接返回null
if (root == null) {
return null;
}
// 一直向左查找
BSTNode<K, V> p = root;
// 找到没有左子树的节点,则是key最小
while (p.left != null) {
p = p.left;
}
return p.value;
}
/
* 向二叉搜索树放入元素,有两种情况
* 1.如果找到key相等的,则进行替换
* 2.如果没找到,则进行添加
*
* @param key 关键字
* @param value 元素值
*/
public void put(K key, V value) {
// 如果树为空,则直接添加
if (root == null) {
root = new BSTNode<>(key, value);
return;
}
// 指针
BSTNode<K, V> p = root;
// 待插入位置的父节点
BSTNode<K, V> parent = null;
// 进行循环
while (p != null) {
// 记录父节点
parent = p;
// 进行比较,-1则key比node.key小,0相等,1则key比node.key大
int compare = key.compareTo(p.key);
// 小于,向左找
if (compare < 0) {
p = p.left;
// 大于,向右找
} else if (compare > 0) {
p = p.right;
} else {
// 找到,则进行替换,然后返回
p.value = value;
return;
}
}
// 没找到,则进行插入
// 需要找到待插入位置的父节点
// 如果小于,则插入父节点的左边
int compare = key.compareTo(parent.key);
if (compare < 0) {
parent.left = new BSTNode<>(key, value);
} else { // 如果大于,则插入父节点的右边
parent.right = new BSTNode<>(key, value);
}
// 没有等于情况,如果等于,则在循环里就找到了
}
}
package com.lzlg.study.algorithm.new2023.bts.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
import java.util.LinkedList;
/
* 求二叉搜索树范围之和(左闭右闭区间)
*
* @author lzlg
* 2023/7/29 10:52
*/
public class BSTSumRange {
/
* 方法1:使用中序遍历
* 区间[low,high]
*
* @param node 节点
* @param low 上范围
* @param high 下范围
* @return 范围之和
*/
public static int sumRange(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
// 和
int sum = 0;
// 指针
TreeNode p = node;
// 栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 循环条件
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
// 优化,如果超过high的范围了,就无须再次循环
if (pop.value > high) {
break;
}
// 在范围内的进行合计
if (pop.value >= low) {
sum += pop.value;
}
// 在范围内的进行合计
// if (pop.value >= low && pop.value <= high) {
// sum += pop.value;
// }
p = pop.right;
}
}
return sum;
}
/
* 方法2:使用递归
* 区间[low,high]
*
* @param node 节点
* @param low 上范围
* @param high 下范围
* @return 范围之和
*/
public static int sumRangeRecursion(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
// 如果节点的值小于low,则在节点的右子树上递归求和
if (node.value < low) {
return sumRangeRecursion(node.right, low, high);
}
// 如果节点的值大于high,则在节点的左子树上递归求和
if (node.value > high) {
return sumRangeRecursion(node.left, low, high);
}
// 如果在合法范围内,则和为当前节点的值+当前节点的左子树的和+当前节点右子树的和
return node.value
+ sumRangeRecursion(node.left, low, high)
+ sumRangeRecursion(node.right, low, high);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(1), 2, new TreeNode(3)),
4,
new TreeNode(new TreeNode(5), 6, new TreeNode(7))
);
System.out.println(sumRangeRecursion(root, 1, 5));
}
}
package com.lzlg.study.algorithm.new2023.bts.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
/
* 找到二叉搜索树两个节点的公共祖先
* 祖先包括节点自己
* 规律:如果两个节点p,q在某节点(也可能为p或q的某一个,或不在p,q上)的两侧
* 则此节点就是p,q的公共祖先
*
* @author lzlg
* 2023/7/29 12:21
*/
public class FindCommonAncestor {
/
* 找到二叉搜索树两个节点的公共祖先
*
* @param root 根节点
* @param p 节点p
* @param q 节点q
* @return 公共祖先节点
*/
public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 指针
TreeNode cur = root;
// 如果p和q在当前指针节点的同一侧,则进行循环
while (p.value > cur.value && q.value > cur.value
|| p.value < cur.value && q.value < cur.value) {
// 大于,则从右找
if (p.value > cur.value) {
cur = cur.right;
} else {
cur = cur.left;
}
}
// 退出循环是,cur即是公共祖先
return cur;
}
public static void main(String[] args) {
// 根节点
TreeNode root = new TreeNode(6);
// 第二层
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(8);
// 第三层
TreeNode node3 = new TreeNode(0);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(7);
TreeNode node6 = new TreeNode(9);
// 第四层
TreeNode node7 = new TreeNode(3);
TreeNode node8 = new TreeNode(5);
// 构建树
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node4.left = node7;
node4.right = node8;
TreeNode ancestor = commonAncestor(root, node1, node2);
System.out.println(ancestor.value);
}
}
package com.lzlg.study.algorithm.new2023.bts.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
/
* 操作二叉搜索树
*
* @author lzlg
* 2023/7/29 9:27
*/
public class OperateBinarySearchTree {
/
* 使用递归删除指定key的节点
*
* @param node 节点
* @param key 指定key
* @return 二叉树根节点
*/
public static TreeNode delete(TreeNode node, int key) {
if (node == null) {
return null;
}
// 如果小于当前节点的值,则向左查找删除
if (key < node.value) {
node.left = delete(node.left, key);
return node;
}
// 如果大于当前节点的值,则向右查找删除
if (key > node.value) {
node.right = delete(node.right, key);
return node;
}
// 以下是找到节点的情况
// 情况1:如果只有右子树
if (node.left == null) {
return node.right;
}
// 情况2:如果只有左子树
if (node.right == null) {
return node.left;
}
// 情况3:如果同时有左右子树
TreeNode s = node.right;
// 找到后继节点
while (s.left != null) {
s = s.left;
}
// 从右子树把后继节点删除
s.right = delete(node.right, s.value);
s.left = node.left;
return s;
}
/
* 向二叉搜索树插入新元素值(保证插入的值没有出现在原二叉树上)
* 此方法会有不必要的赋值操作
*
* @param node 节点
* @param value 元素值
* @return 二叉树根节点
*/
public static TreeNode add(TreeNode node, int value) {
// 如果找到插入位置,则返回新节点
if (node == null) {
return new TreeNode(value);
}
// 如果小于当前节点的value,则向左查找
if (value < node.value) {
node.left = add(node.left, value);
// 如果大于当前节点的value,则向右查找
} else if (value > node.value) {
node.right = add(node.right, value);
}// 没有相等的情况(题目规定)
return node;
}
/
* 获取二叉搜索树指定key的节点
*
* @param node 节点
* @param key 指定key
* @return 节点
*/
public static TreeNode get(TreeNode node, int key) {
// 没找到返回null
if (node == null) {
return null;
}
// 小于,向左找
if (key < node.value) {
return get(node.left, key);
}
// 大于,向右找
if (key > node.value) {
return get(node.right, key);
}
// 相等,直接返回
return node;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(1), 2, new TreeNode(3)),
4,
new TreeNode(new TreeNode(5), 6, new TreeNode(7))
);
System.out.println("begin=====二叉搜索树中序遍历:");
print(root);
System.out.println("========get========");
TreeNode node = get(root, 6);
print(node);
System.out.println("========add========");
node = add(root, 9);
print(node);
System.out.println("========delete========");
node = delete(root, 9);
print(node);
}
/
* 中序打印
*
* @param node 节点
*/
private static void print(TreeNode node) {
if (node == null) {
return;
}
print(node.left);
System.out.println(node.value);
print(node.right);
}
}
package com.lzlg.study.algorithm.new2023.bts.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
/
* 根据前序遍历结果,构建二叉搜索树
* 给定的遍历结果数组没有重复值,且至少有一个元素
*
* @author lzlg
* 2023/7/29 11:32
*/
public class PrevOrderBuildBST {
/
* 方法1:使用插入方法
*
* @param prevOrder 前序遍历结果
* @return 二叉搜索树
*/
public static TreeNode buildBST(int[] prevOrder) {
// 根节点,因为是前序遍历节点,数组第一个元素(下标为0)是根节点元素值
TreeNode root = new TreeNode(prevOrder[0]);
// 从第二个元素开始遍历数组
for (int j = 1; j < prevOrder.length; j++) {
// 依次进行插入
insert(root, prevOrder[j]);
}
return root;
}
/
* 递归插入方法
*
* @param node 节点
* @param value 待插入值
* @return 二叉树节点
*/
private static TreeNode insert(TreeNode node, int value) {
if (node == null) {
return new TreeNode(value);
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
}
return node;
}
/
* 方法2:使用递归+边界法
*
* @param prevOrder 前序遍历结果
* @return 二叉搜索树
*/
public static TreeNode recursionBuildBST(int[] prevOrder) {
return recursionBuildBST(prevOrder, Integer.MAX_VALUE);
}
// 方法2使用的数组下标
static int i = 0;
/
* 方法2:使用递归+上限法
*
* @param prevOrder 前序遍历结果
* @param max 上限
* @return 二叉搜索树
*/
private static TreeNode recursionBuildBST(int[] prevOrder, int max) {
// 如果当前下标等于数组长度,则返回null
if (i == prevOrder.length) {
return null;
}
// 当前值
int value = prevOrder[i];
// 如果大于上限,返回null
if (value > max) {
return null;
}
// 创建新节点
TreeNode node = new TreeNode(value);
i++;
// 新节点的左子树的上限是当前节点的value
node.left = recursionBuildBST(prevOrder, value);
// 新节点的右子树的上限是当前节点的max
node.right = recursionBuildBST(prevOrder, max);
return node;
}
/
* 方法3:使用分治法
*
* @param prevOrder 前序遍历结果
* @return 二叉搜索树
*/
public static TreeNode partitionBuildBST(int[] prevOrder) {
return partitionBuildBST(prevOrder, 0, prevOrder.length - 1);
}
/
* 方法3:使用分治法,递归操作
*
* @param prevOrder 前序遍历结果
* @param start 二叉树起点
* @param end 二叉树终点
* @return 二叉搜索树
*/
private static TreeNode partitionBuildBST(int[] prevOrder, int start, int end) {
// 如果起点大于终点,则返回null
if (start > end) {
return null;
}
// 根节点的值就是起点下标对应的数组元素
int rootValue = prevOrder[start];
// 创建根节点
TreeNode root = new TreeNode(rootValue);
// 找到分界下标,初始值是起点+1
int partitionIndex = start + 1;
while (partitionIndex <= end) {
// 如果分界下标的元素值大于根节点的,则找到了右子树的根节点下标
if (prevOrder[partitionIndex] > rootValue) {
break;
}
partitionIndex++;
}
// 递归调用创建左子树
root.left = partitionBuildBST(prevOrder, start + 1, partitionIndex - 1);
// 递归调用创建右子树
root.right = partitionBuildBST(prevOrder, partitionIndex, end);
return root;
}
public static void main(String[] args) {
int[] prevOrder = {8, 5, 1, 7, 9, 10, 12};
TreeNode root = buildBST(prevOrder);
print(root);
}
/
* 前序打印
*
* @param node 节点
*/
private static void print(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.value);
print(node.left);
print(node.right);
}
}
package com.lzlg.study.algorithm.new2023.bts.quiz;
import com.lzlg.study.algorithm.new2023.tree.TreeNode;
import java.util.LinkedList;
/
* 验证是否是二叉搜索树
*
* @author lzlg
* 2023/7/29 9:46
*/
public class ValidateBinarySearchTree {
/
* 验证是否是二叉搜索树
* 使用中序遍历,因为中序遍历是有序的
*
* @param root 二叉树根节点
* @return 结果
*/
public static boolean validBST(TreeNode root) {
if (root == null) {
return true;
}
// 当前指针
TreeNode p = root;
// 使用栈
LinkedList<TreeNode> stack = new LinkedList<>();
// 使用prev记录上次的值,用于和当前值比较,初始值为long的最小值
long prev = Long.MIN_VALUE;
// 开始循环
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
// 如果上次的值大于等于当前值,则证明不是二叉搜索树
// 因为中序遍历二叉搜索树是有序的
if (prev >= pop.value) {
return false;
}
// 更新上次的值
prev = pop.value;
// 向右
p = pop.right;
}
}
return true;
}
// 注意2:previous不能是方法内非对象变量
// 如果是方法局部变量(非对象),则每个方法的previous有可能不同
// 否则在某个子树遍历更新时不能及时通知到父节点的判断,造成判断错误
// =如果必须在方法内使用,则可以使用AtomicLong对象来代替
private static long previous = Long.MIN_VALUE;
/
* 验证是否是二叉搜索树,递归实现
* 使用中序遍历,因为中序遍历是有序的
*
* @param node 节点
* @return 结果
*/
public static boolean recursionValidBST(TreeNode node) {
// 如果节点为null,则是合法的
if (node == null) {
return true;
}
// 判断左子树是否合法
boolean leftValid = recursionValidBST(node.left);
// 注意1:使用此判断能快速返回判断节点,不再进行右子树的判断逻辑
// 如果不使用此判断,则虽然判断左子树是非法的
// 但是判断右子树的代码还得继续判断,这实际上是没必要的
if (!leftValid) {
return false;
}
// 如果前一个节点的值大于当前节点的,则是不合法的
if (previous >= node.value) {
return false;
}
// 更新当前节点的值
previous = node.value;
// 判断右子树是否合法
boolean rightValid = recursionValidBST(node.right);
// return leftValid && rightValid;
return rightValid;
}
/
* 使用上下界进行二叉搜索树合法性的判断
* 左子节点的边界是(父节点的左边界,父节点的value)
* 右子节点的边界是(父节点的value,父节点的右边界)
*
* @param node 节点
* @return 结果
*/
public static boolean borderValidBST(TreeNode node) {
return borderValidBST(node, Long.MIN_VALUE, Long.MAX_VALUE);
}
/
* 使用上下边界验证是否是合法的二叉搜索树
*
* @param node 当前节点
* @param min 节点左边界
* @param max 节点右边界
* @return 结果
*/
private static boolean borderValidBST(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
// 超出边界,返回null(注意合法边界是开区间)
if (node.value <= min || node.value >= max) {
return false;
}
// 进行左子树的判断
boolean leftValid = borderValidBST(node.left, min, node.value);
// 进行右子树的判断
boolean rightValid = borderValidBST(node.right, node.value, max);
return leftValid && rightValid;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(1), 2, new TreeNode(3)),
4,
new TreeNode(new TreeNode(5), 6, new TreeNode(7))
);
root = new TreeNode(new TreeNode(1), 1, null);
root = new TreeNode(
new TreeNode(new TreeNode(1), 2, new TreeNode(3)),
5,
new TreeNode(new TreeNode(4), 6, new TreeNode(7))
);
root = new TreeNode(
null,
3,
new TreeNode(new TreeNode(5), 4, null)
);
System.out.println("===是否是BST树:");
System.out.println(borderValidBST(root));
}
}
package com.lzlg.study.algorithm.new2023.bts;
/
* 测试
*
* @author lzlg
* 2023/7/28 10:17
*/
public class TestBinarySearchTree {
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.put(4, "Haha");
tree.put(2, "La");
tree.put(6, "Ben");
tree.put(1, "She");
tree.put(3, "Xia");
tree.put(7, "Da");
tree.put(5, "OOO");
tree.print(node -> System.out.println(node.key + ":" + node.value));
System.out.println("=================");
tree.put(8, "Fuck");
tree.print(node -> System.out.println(node.key + ":" + node.value));
System.out.println(tree.get(1));
System.out.println("=================");
System.out.println(tree.former(4));
System.out.println("=================");
System.out.println(tree.latter(4));
System.out.println("=================");
// tree.recursionDelete(5);
// tree.print(node -> System.out.println(node.key + ":" + node.value));
// System.out.println("=================");
System.out.println(tree.less(6));
System.out.println("=================");
System.out.println(tree.greater(6));
System.out.println("=================");
System.out.println(tree.between(3, 7));
}
}
二叉平衡树
package com.lzlg.study.algorithm.new2023.avl;
/
* AVL树,通过旋转达到左右平衡的自平衡二叉树
* 左右子节点的高度不超过1,旋转情况有如下4种:
* 1.左左(LL):节点的左子节点的高度比右子节点的高度>1
* 且节点的左子节点的左子节点的高度大于等于节点的左子节点的右子节点的高度
* 当前节点右旋
* <p>
* 2.左右(LR):节点的左子节点的高度比右子节点的高度>1
* 且节点的左子节点的左子节点的高度小于节点的左子节点的右子节点的高度
* 当前节点的左子节点左旋后,当前节点右旋
* <p>
* 3.右左(LL):节点的左子节点的高度比右子节点的高度<-1
* 且节点的右子节点的左子节点的高度大于节点的右子节点的右子节点的高度
* 当前节点的右子节点右旋后,当前节点左旋
* <p>
* 4.右右(LR):节点的左子节点的高度比右子节点的高度<-1
* 且节点的右子节点的左子节点的高度小于等于节点的右子节点的右子节点的高度
* 当前节点左旋
*
* @author lzlg
* 2023/7/30 9:34
*/
public class AVLTree {
// AVL树的根节点
AVLNode root;
/
* 添加或替换指定key的节点元素值
*
* @param key 关键字key
* @param value 元素值
*/
public void put(int key, Object value) {
root = doPut(root, key, value);
}
/
* 递归进行添加或替换指定key的节点元素值
*
* @param node 节点
* @param key 关键字key
* @param value 元素值
* @return 新节点
*/
private AVLNode doPut(AVLNode node, int key, Object value) {
// 如果node为null,则直接创建新节点返回
if (node == null) {
return new AVLNode(key, value);
}
// 如果找到对应key的节点,则进行替换
if (key == node.key) {
node.value = value;
return node;
}
// 如果key小于当前节点的key,则向左查找
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else {
// 如果大于,则向右查找
node.right = doPut(node.right, key, value);
}
// 更新节点高度
updateHeight(node);
// 进行平衡调整
return balance(node);
}
/
* 删除指定key对应的节点
*
* @param key 关键字key
*/
public void remove(int key) {
root = doRemove(root, key);
}
/
* 删除指定key对应的节点
*
* @param node 当前节点
* @param key 关键字key
* @return 新节点
*/
private AVLNode doRemove(AVLNode node, int key) {
// 如果节点为null,则直接返回null
if (node == null) {
return null;
}
// 如果key小于当前节点的key,则向左查找
if (key < node.key) {
node.left = doRemove(node.left, key);
// 如果大于,则向右查找
} else if (key > node.key) {
node.right = doRemove(node.right, key);
} else {// 如果找到
// 情况1:无左右子树
if (node.left == null && node.right == null) {
// 直接返回null,就把当前节点(自身)删除了
return null;
}
// 情况2:只有右子树
if (node.left == null) {
node = node.right;
// 情况3:只有左子树
} else if (node.right == null) {
node = node.left;
} else {// 情况4:同时有左右子树
// 找到当前待删除节点的后继节点
AVLNode s = node.right;
while (s.left != null) {
s = s.left;
}
// 循环过后,则s是后继节点
// 从当前节点的右子树中删除该后继节点,并赋值给后继节点的右子树
s.right = doRemove(node.right, s.key);
// 把当前节点的左子树赋值给后继节点
s.left = node.left;
}
}
// 更新节点高度
updateHeight(node);
// 进行平衡调整
return balance(node);
}
/
* 进行二叉树的平衡
*
* @param node 当前节点
* @return 新的节点
*/
public AVLNode balance(AVLNode node) {
if (node == null) {
return null;
}
// 获得当前节点的平衡因子
int bf = balanceFactor(node);
// 不平衡1:如果大于1,则是左子树高
if (bf > 1) {
// 判断节点的左子树的平衡因子
// 如果大于等于0则节点的左子树的左子节点高,是情况左左LL
if (balanceFactor(node.left) >= 0) {
// 直接右旋
return rightRotate(node);
} else {
// 如果小于0,则节点的左子树的右子节点高,是情况左右LR
// 先左旋,再右旋
return leftRightRotate(node);
}
}
// 不平衡2:如果小于-1,则是右子树高
if (bf < -1) {
// 判断节点的右子树的平衡因子
// 如果大于等于0则节点的右子树的左子节点高,是情况右左RL
if (balanceFactor(node.right) >= 0) {
// 先右旋后左旋
return rightLeftRotate(node);
} else {
// 如果小于0,则节点的右子树的右子节点高,是情况右右RR
// 直接左旋
return leftRotate(node);
}
}
// 如果是平衡状态,则直接返回原节点
return node;
}
/
* 左旋
*
* @param node 要旋转的节点
* @return 新的节点
*/
public AVLNode leftRotate(AVLNode node) {
// 找到节点的右孩子
AVLNode rightChild = node.right;
// 如果右孩子有左子树
AVLNode leftGrandson = rightChild.left;
// 右孩子的左节点指向原节点
rightChild.left = node;
// 原节点的左子节点指向右孩子的左子树
node.right = leftGrandson;
// 更新原节点高度(必须先更新,因为旋转后是低于右孩子的层的)
updateHeight(node);
// 更新右孩子节点的高度
updateHeight(rightChild);
// 右旋后,右孩子节点为新的根节点
return rightChild;
}
/
* 右旋
*
* @param node 要旋转的节点
* @return 新的节点
*/
public AVLNode rightRotate(AVLNode node) {
// 找到节点的左孩子
AVLNode leftChild = node.left;
// 如果左孩子有右子树,则需放置在原节点的左子节点上
AVLNode rightGrandson = leftChild.right;
// 旋转后节点的左孩子的右子节点是原节点
leftChild.right = node;
// 原节点的左子树为左孩子的右子节点
node.left = rightGrandson;
// 更新原节点(必须先更新,因为变成原左孩子的子节点了)的高度
updateHeight(node);
// 更新原左孩子节点的高度
updateHeight(leftChild);
// 原左孩子节点变为根节点返回
return leftChild;
}
/
* 左右旋
*
* @param node 要旋转的节点
* @return 新的节点
*/
public AVLNode leftRightRotate(AVLNode node) {
// 左子节点先左旋,左旋返回的节点是当前节点新的左子节点
node.left = leftRotate(node.left);
// 再对当前节点右旋,返回新节点
return rightRotate(node);
}
/
* 右左旋
*
* @param node 要旋转的节点
* @return 新的节点
*/
public AVLNode rightLeftRotate(AVLNode node) {
// 当前节点的右子节点先右旋,右旋返回的是当前节点的新右子节点
node.right = rightRotate(node.right);
// 当前节点左旋,并返回新节点
return leftRotate(node);
}
/
* 获取节点的高度
*
* @param node 节点
* @return 高度
*/
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
/
* 更新节点的高度
*
* @param node 节点
*/
private void updateHeight(AVLNode node) {
// 节点的新高度=左右子节点高度中最大的+1
node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
/
* 判断节点是否需要进行旋转
* 返回1,0,-1则不需要
* 返回>1则左边高于右边
* 返回<-1则右边高于左边
*
* @param node 当前节点
* @return 平衡因子
*/
private int balanceFactor(AVLNode node) {
return height(node.left) - height(node.right);
}
private static class AVLNode {
// 关键字key
int key;
// 节点存储的元素值
Object value;
// 左子节点
AVLNode left;
// 右子节点
AVLNode right;
// 节点的高度,初始值为1
int height;
public AVLNode(int key, Object value) {
this.key = key;
this.value = value;
this.height = 1;
}
public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.height = 1;
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.put(9, "Descent");
tree.put(5, "Machine");
tree.put(3, "AI");
tree.print(tree.root);
}
/
* 前序遍历进行打印
*
* @param node 节点
*/
private void print(AVLNode node) {
if (node == null) {
return;
}
System.out.println("key: " + node.key + ", value: " + node.value);
print(node.left);
print(node.right);
}
}
package com.lzlg.study.algorithm.new2023.avl;
import static com.lzlg.study.algorithm.new2023.avl.RedBlackTree.Color.BLACK;
import static com.lzlg.study.algorithm.new2023.avl.RedBlackTree.Color.RED;
/
* 红黑树
* 红黑树的特性:
* 1.节点的颜色要么是红色要么是黑色
* 2.所有的null都是黑色的
* 3.根节点是黑色的
* 4.红色节点不能相邻,即一个红色节点不能有红色的子节点
* 5.从根节点到每个叶子节点的路径经过的黑色节点的数量都是一样的(黑色完美平衡)
*
* @author lzlg
* 2023/7/30 12:47
*/
public class RedBlackTree {
// 根节点
RedBlackNode root;
/
* 添加或更新指定key的节点元素值
*
* @param key 指定key
* @param value 元素值
*/
public void put(int key, Object value) {
// 记录节点的父节点
RedBlackNode parent = null;
// 指针
RedBlackNode p = root;
// 循环找到key对应的节点
while (p != null) {
// 父节点
parent = p;
// 小于,向左找
if (key < p.key) {
p = p.left;
// 大于向右找
} else if (key > p.key) {
p = p.right;
} else {
// 如果找到,则进行替换
p.value = value;
return;
}
}
// 没找到,则进行添加
RedBlackNode node = new RedBlackNode(key, value);
// 没有父节点,则赋值给根节点
if (parent == null) {
root = node;
// 如果小于父节点的key,则是父节点的左孩子
} else if (key < parent.key) {
parent.left = node;
// 新节点的父节点是parent
node.parent = parent;
} else {
// 如果大于父节点的key,则是父节点的右孩子
parent.right = node;
// 新节点的父节点是parent
node.parent = parent;
}
// 因为新添加的节点颜色是红色,需进行红黑树的调整
fixTree(node);
}
/
* 红黑树的调整有两种方式:
* 一个是变色
* 一个是旋转,如果变色解决不了,则进行旋转
* <p>
* 调整红黑树,新插入的节点都是红色
* 1.如果插入的节点是根节点,则变为黑色
* 2.如果插入的节点的父节点是黑色,则树的红黑性质不变,无需调整
* 3.如果插入的节点的父节点是红色,则有:
* 1)如果叔叔节点是红色,则
* 1.1)把父节点变为黑色,为保持平衡,也把叔叔节点变为黑色
* 1.2)把爷爷节点变为红色,如果不变色,则此路径的黑色数量过多(不符合性质5)
* 1.3)然后递归1.1)和1.2)的过程,直到根节点
* 2)如果叔叔节点是黑色,则
* 2.1)如果父节点是左孩子,插入节点是左孩子,则是LL不平衡(右旋)
* 2.1)如果父节点是左孩子,插入节点是右孩子,则是LR不平衡(父节点左旋,爷爷右旋)
* 2.1)如果父节点是右孩子,插入节点是左孩子,则是RL不平衡(父节点右旋,爷爷左旋)
* 2.1)如果父节点是右孩子,插入节点是右孩子,则是RR不平衡(左旋)
*
* @param node 当前节点
*/
private void fixTree(RedBlackNode node) {
// 如果是根节点,则变为黑色
if (node == root) {
node.color = BLACK;
return;
}
// 如果父节点是黑色,则直接返回
if (isBlack(node.parent)) {
return;
}
// =========父节点是红色=========
// 父节点
RedBlackNode parent = node.parent;
// 叔叔节点
RedBlackNode uncle = node.uncle();
// 爷爷节点
RedBlackNode grandparent = parent.parent;
// 1.如果叔叔节点是红色
if (isRed(uncle)) {
// 修改父节点和叔叔节点的颜色为黑色
parent.color = BLACK;
uncle.color = BLACK;
// 修改爷爷节点的颜色为红色
grandparent.color = RED;
// 进行递归调用
fixTree(grandparent);
return;
}
// 2.如果叔叔节点是黑色
// 如果父节点是左孩子,插入节点是左孩子,则变色后进行右旋
if (parent.isLeftChild() && node.isLeftChild()) {
// 父节点变为黑色
parent.color = BLACK;
// 爷爷节点变为红色
grandparent.color = RED;
// 爷爷节点进行右旋
rightRotate(grandparent);
// 如果父节点是左孩子,插入节点是右孩子
} else if (parent.isLeftChild() && !node.isLeftChild()) {
// 父节点进行左旋
leftRotate(parent);
// 旋转后,父节点变为新插入的节点了
node.color = BLACK;
// 爷爷节点变为红色
grandparent.color = RED;
// 爷爷节点进行右旋
rightRotate(grandparent);
// 如果父节点是右孩子,插入节点是左孩子
} else if (!parent.isLeftChild() && node.isLeftChild()) {
// 父节点右旋
rightRotate(parent);
// 旋转后,父节点变为新插入的节点了
node.color = BLACK;
// 爷爷节点变为红色
grandparent.color = RED;
// 爷爷节点进行左旋
leftRotate(grandparent);
// 如果父节点是右孩子,插入节点是右孩子
} else if (!parent.isLeftChild() && !node.isLeftChild()) {
// 父节点变为黑色
parent.color = BLACK;
// 爷爷节点变为红色
grandparent.color = RED;
// 爷爷节点进行左旋
leftRotate(grandparent);
}
}
/
* 删除指定key的节点
*
* @param key 指定key
*/
public void remove(int key) {
// 查找待删除节点
RedBlackNode deleted = findNode(key);
// 没有找到,直接返回null
if (deleted == null) {
return;
}
// 进行删除节点的递归操作
doRemove(deleted);
}
/
* 删除节点,有如下情况:
* 1.如果删除节点有两个孩子
* 则通过和替换节点交换key和value
* 转化为没有孩子节点和只有一个孩子节点的情况
* 下次递归进行删除
* <p>
* 2.如果待删除节点是根节点
* 1)如果是没有孩子的情况,直接置为null
* 2)如果是只有一个孩子的情况
* 则通过把根节点的key和value赋值给替换节点
* 再将根节点的左右孩子置为null,由此删除
* <p>
* 3.如果待删除节点不是根节点
* 1)如果是没有孩子的情况
* 则判断是父节点左孩子节点还是右孩子节点
* 并把父节点相应的孩子节点置为null
* 同时待删除节点的parent置为null--help GC
* 2)如果是只有一个孩子的情况
* 则判断是父节点左孩子节点还是右孩子节点
* 并把父节点相应的孩子节点置为替换节点
* 同时把替换节点的parent指向父节点
* 同时待删除节点的left,right,parent都置为null--help GC
* <p>
* [删除黑色叶子节点会导致平衡失败(因为违反性质5),删除红色叶子节点则不会]
* <p>
* 4.删除节点的判断逻辑
* 1)如果删除的节点是红色的,不会造成路径上的黑色节点数量的变更,因此可以直接删除
* 2)如果删除的节点是黑色的
* 2.1)如果此节点是叶子节点,则需要进行{复杂调整}--这是在删除前进行的调整,使用deleted
* 2.2)如果此节点只有一个孩子节点(替换节点),则
* 如果该孩子节点(替换节点)是红色的,则可在删除后,直接变为黑色
* 否则需要进行{复杂调整}--这是在删除后进行的调整,使用replaced
*
* @param deleted 待删除节点
*/
private void doRemove(RedBlackNode deleted) {
// 找到待删除节点的替换节点
RedBlackNode replaced = replacedByRemoved(deleted);
// 待删除节点的父节点
RedBlackNode parent = deleted.parent;
// 如果替换节点没有孩子节点
if (replaced == null) {
// 如果删除的是根节点,则直接置为null
if (deleted == root) {
root = null;
} else {
// 如果删除的是黑色节点,则需要进行复杂调整
if (isBlack(deleted)) {
// 删除前调整-复杂调整
fixDoubleBlack(deleted);
}
// 如果待删除节点是父节点的左孩子,则将父节点的左孩子置为null
if (deleted.isLeftChild()) {
parent.left = null;
} else {
// 如果待删除节点是父节点的右孩子,则将父节点的右孩子置为null
parent.right = null;
}
// help GC
deleted.parent = null;
}
return;
}
// 如果待删除节点只有一个孩子节点
if (replaced.left == null || replaced.right == null) {
// 如果删除的是根节点
// 此时根节点只会有一个红色的节点,即replaced
if (deleted == root) {
// 将根节点的key和value替换为replaced节点的
root.key = replaced.key;
root.value = replaced.value;
// 将根节点的左右子节点置空
root.left = root.right = null;
} else {
// 如果待删除节点是父节点的左孩子
if (deleted.isLeftChild()) {
// 则将父节点的left指向替换节点
parent.left = replaced;
} else {// 如果待删除节点是父节点的右孩子
// 则将父节点的right指向替换节点
parent.right = replaced;
}
// 不要忘了把replaced节点的父节点改为parent
replaced.parent = parent;
// help GC
deleted.left = deleted.right = deleted.parent = null;
// 如果删除的节点是黑色的,且替换的节点也是黑色的,则需要进行复杂调整
if (isBlack(deleted) && isBlack(replaced)) {
// 删除后调整-复杂调整
fixDoubleBlack(replaced);
} else {
// 其他情况,则需要更新替换节点的颜色为黑色
replaced.color = BLACK;
}
}
return;
}
// 如果待删除节点有两个孩子节点
// 可通过替换key和value值,将待删除节点和替换节点交换
// 这样问题可简化成只有一个孩子节点或没有孩子节点的问题
swapKey(deleted, replaced);
swapValue(deleted, replaced);
// 替换完成后,使用替换的节点再次递归删除
doRemove(replaced);
}
/
* 复杂调整,有以下情况
* 1.如果被调整节点(假如是父节点的左节点)的兄弟节点是红色的(此兄弟节点的子节点必定都是黑色-因为红色不能相邻)
* 则先把父节点进行左旋,然后把父节点的颜色变为红色,上个兄弟节点变为黑色,这样才能保证平衡
* 则被调整节点的兄弟节点(非原兄弟节点)则变为黑色了,转化成下面两种情况
* <p>
* 2.被调整节点为黑色,且兄弟节点为黑色,且兄弟节点的两个孩子节点也是黑色
* 先将兄弟节点变红(此时该子树少了一个黑色节点)
* 2.1)如果父节点是红色,则父节点变黑(通过变黑,增加了一个黑色节点)
* 2.2)如果父节点是黑色,则父节点回到的开始时双黑的情况,则使用父节点递归调用,调整节点颜色
* <p>
* 3.被调整节点为黑色,且兄弟节点为黑色,且兄弟节点的其中至少一个孩子节点是红色
* 3.1)如果兄弟节点是左孩子,且兄弟节点的左孩子是红色,则是LL情况
* 先把父节点进行右旋,然后兄弟节点的颜色变为原父节点颜色,原父节点颜色变为黑色
* 兄弟节点的左孩子变为黑色,达到平衡
* 3.2)如果兄弟节点是左孩子,且兄弟节点的右孩子是红色,则是LR情况
* 先把兄弟节点的颜色变为原父节点颜色(否则会因为旋转丢失兄弟记得的右孩子指针)
* 先根据兄弟节点进行左旋,然后根据父节点进行右旋
* 然后原父节点颜色变为黑色,兄弟节点的左孩子(已经是黑色,这一步可不做)变为黑色,达到平衡
*
* @param node 被调整的节点(一定是黑色节点)
*/
private void fixDoubleBlack(RedBlackNode node) {
// 如果调整到根部了,可结束调整
if (node == root) {
return;
}
// 父节点
RedBlackNode parent = node.parent;
// 兄弟节点
RedBlackNode sibling = node.sibling();
// 如果兄弟节点是红色的
if (isRed(sibling)) {
// 且被调整节点是父节点的左孩子
if (node.isLeftChild()) {
// 父节点左旋
leftRotate(parent);
} else {// 若调整节点是父节点的右孩子
// 则父节点右旋
rightRotate(parent);
}
// 保证旋转后的平衡
// 原父节点因为变成兄弟节点的子节点,且获得了一个黑色的子节点,因此需要变成红色
parent.color = RED;
// 兄弟节点变为父节点了,因红色不能相邻(父节点变为红色了),因此需要变成黑色
sibling.color = BLACK;
// 转化为其他情况后,进行递归调用
fixDoubleBlack(node);
return;
}
// 此时兄弟节点是黑色
if (sibling != null) {
// 兄弟节点的子节点都是黑色的情况
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 先将兄弟节点变红
sibling.color = RED;
// 如果父节点颜色是红色,则直接把父节点变为黑色
if (isRed(parent)) {
parent.color = BLACK;
} else {
// 否则递归调用,调整父节点以上的节点的颜色
fixDoubleBlack(parent);
}
} else {// 兄弟节点的子节点至少有一个是红色的情况
// 如果兄弟节点是左孩子,且兄弟节点的左孩子节点是红色
if (sibling.isLeftChild() && isRed(sibling.left)) {
// 父节点进行右旋
rightRotate(parent);
// 兄弟节点的左孩子节点颜色变为黑色
sibling.left.color = BLACK;
// 兄弟节点的颜色是原父节点的颜色
sibling.color = parent.color;
// 父节点的颜色变为黑色
// 如果兄弟节点是左孩子,且兄弟节点的右孩子节点是红色
} else if (sibling.isLeftChild() && isRed(sibling.right)) {
// 先将父节点的颜色赋值给兄弟节点的左孩子,防止旋转后丢失指向右孩子的指针
sibling.right.color = parent.color;
// 根据兄弟节点左旋
leftRotate(sibling);
// 根据父节点右旋
rightRotate(parent);
// 父节点的颜色变为黑色
// 如果兄弟节点是右孩子,且兄弟节点的右孩子节点是红色
} else if (!sibling.isLeftChild() && isRed(sibling.right)) {
// 父节点进行左旋
leftRotate(parent);
// 兄弟节点的右孩子节点颜色变为黑色
sibling.right.color = BLACK;
// 兄弟节点的颜色是原父节点的颜色
sibling.color = parent.color;
// 父节点的颜色变为黑色
// 如果兄弟节点是右孩子,且兄弟节点的左孩子节点是红色
} else if (!sibling.isLeftChild() && isRed(sibling.left)) {
// 先把兄弟节点的左孩子的颜色改为父节点的颜色,防止旋转后丢失指向右孩子的指针
sibling.left.color = parent.color;
// 根据兄弟节点右旋
rightRotate(sibling);
// 根据父节点左旋
leftRotate(parent);
// 父节点的颜色变为黑色
}
// 父节点的颜色变为黑色
parent.color = BLACK;
}
} else {
// 如果没有兄弟节点,则父节点进行调整
fixDoubleBlack(parent);
}
}
/
* 交换两个节点的key
*
* @param node1 节点1
* @param node2 节点2
*/
private void swapKey(RedBlackNode node1, RedBlackNode node2) {
int k = node1.key;
node1.key = node2.key;
node2.key = k;
}
/
* 交换两个节点的value
*
* @param node1 节点1
* @param node2 节点2
*/
private void swapValue(RedBlackNode node1, RedBlackNode node2) {
Object v = node1.value;
node1.value = node2.value;
node2.value = v;
}
/
* 根据指定的key查找对应的节点
*
* @param key 指定的key
* @return 节点
*/
private RedBlackNode findNode(int key) {
RedBlackNode p = root;
// 循环查找
while (p != null) {
if (key < p.key) {
p = p.left;
} else if (key > p.key) {
p = p.right;
} else {
// 找到返回节点
return p;
}
}
return null;
}
/
* 根据删除的节点查找替换此删除节点的节点
*
* @param deleted 待删除节点
* @return 替换删除节点的节点
*/
private RedBlackNode replacedByRemoved(RedBlackNode deleted) {
// 如果待删除节点无子节点,则直接返回null
if (deleted.left == null && deleted.right == null) {
return null;
}
// 如果待删除节点的左孩子节点为空,则返回右孩子节点
if (deleted.left == null) {
return deleted.right;
}
// 如果待删除节点的右孩子节点为空,则返回左孩子节点
if (deleted.right == null) {
return deleted.left;
}
// 如果待删除节点有左右孩子节点,则查找后继节点
RedBlackNode s = deleted.right;
while (s.left != null) {
s = s.left;
}
return s;
}
/
* 右旋
* 需要相应更新节点的父节点等信息
*
* @param node 要旋转的节点
*/
private void rightRotate(RedBlackNode node) {
// 当前节点的父节点
RedBlackNode parent = node.parent;
// ==============进行旋转===============
// 当前节点的左孩子
RedBlackNode leftChild = node.left;
// 保留左孩子的右子节点
RedBlackNode rightGrandson = leftChild.right;
// 把左孩子的right指向当前节点
leftChild.right = node;
// 更新当前节点的左孩子
node.left = rightGrandson;
// ==============修改父节点指针===============
// 左孩子节点代替了父节点,因此当前节点的父节点是孩子节点的父节点
leftChild.parent = parent;
// 判空判断:有时可能没有左孩子的右子节点
if (rightGrandson != null) {
// 左孩子的右子节点称为了节点的左孩子,因此它的父节点是当前节点
rightGrandson.parent = node;
}
// 当前节点的父节点变为左孩子节点
node.parent = leftChild;
// =========当前节点的父节点的子节点需调整===========
// 如果当前节点的父节点为null(是根节点),则root就是旋转后的新节点
if (parent == null) {
root = leftChild;
return;
}
// 如果当前节点是父节点的左子节点,则父节点的left指向旋转后新节点
if (parent.left == node) {
parent.left = leftChild;
} else {
// 如果是右子节点,则父节点的right指向旋转后新节点
parent.right = leftChild;
}
}
/
* 左旋
*
* @param node 要旋转的节点
*/
private void leftRotate(RedBlackNode node) {
// 当前节点的父节点
RedBlackNode parent = node.parent;
// ==============进行旋转===============
// 当前节点的右孩子
RedBlackNode rightChild = node.right;
// 保留右孩子的左子节点
RedBlackNode leftGrandson = rightChild.left;
// 把右孩子的left指向当前节点
rightChild.left = node;
// 更新当前节点的右孩子
node.right = leftGrandson;
// ==============修改父节点指针===============
// 右孩子节点代替了父节点,因此当前节点的父节点是孩子节点的父节点
rightChild.parent = parent;
// 判空判断:有时可能没有右孩子的左子节点
if (leftGrandson != null) {
// 右孩子的左子节点称为了节点的右孩子,因此它的父节点是当前节点
leftGrandson.parent = node;
}
// 当前节点的父节点变为右孩子节点
node.parent = rightChild;
// =========当前节点的父节点的子节点需调整===========
// 如果当前节点的父节点为null(是根节点),则root就是旋转后的新节点
if (parent == null) {
root = rightChild;
return;
}
// 如果当前节点是父节点的左子节点,则父节点的left指向旋转后新节点
if (parent.left == node) {
parent.left = rightChild;
} else {
// 如果是右子节点,则父节点的right指向旋转后新节点
parent.right = rightChild;
}
}
/
* 判断节点颜色是否是红色
*
* @param node 节点
* @return 结果
*/
private boolean isRed(RedBlackNode node) {
return node != null && node.color == RED;
}
/
* 判断节点颜色是否是黑色
*
* @param node 节点
* @return 结果
*/
private boolean isBlack(RedBlackNode node) {
// 第一种写法
// return !isRed(node);
// 第二种写法
return node == null || node.color == BLACK;
}
/
* 节点类
*/
static class RedBlackNode {
// 关键字key
int key;
// 元素值
Object value;
// 左子节点
RedBlackNode left;
// 右子节点
RedBlackNode right;
// 父节点
RedBlackNode parent;
// 节点颜色,初始为红色
Color color;
public RedBlackNode(int key, Object value) {
this.key = key;
this.value = value;
this.color = RED;
}
/
* 当前节点是否是左子节点
*
* @return 结果
*/
public boolean isLeftChild() {
return parent != null && parent.left == this;
}
/
* 当前节点的叔叔节点
*
* @return 叔叔节点
*/
public RedBlackNode uncle() {
// 没有父节点或没有爷爷节点,则必没有叔叔节点
if (parent == null || parent.parent == null) {
return null;
}
// 如果父节点是爷爷的左子节点,则叔叔节点是爷爷的右子节点
if (parent.isLeftChild()) {
return parent.parent.right;
}
// 否则是爷爷的左子节点
return parent.parent.left;
}
/
* 当前节点的兄弟节点
*
* @return 兄弟节点
*/
public RedBlackNode sibling() {
// 如果没有父节点,一定没有兄弟节点
if (parent == null) {
return null;
}
// 如果当前节点是父节点的左子节点,则兄弟节点是父节点的右子节点
if (this.isLeftChild()) {
return parent.right;
}
// 否则是父节点的左子节点
return parent.left;
}
}
/
* 颜色类
*/
enum Color {
RED, BLACK;
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
tree.put(9, "哈哈");
tree.put(7, "很好");
tree.put(6, "不错");
tree.put(5, "卧室");
tree.put(3, "枚举");
tree.print(tree.root);
System.out.println("=========================");
tree.remove(9);
tree.print(tree.root);
}
/
* 前序遍历打印
*
* @param node 节点
*/
private void print(RedBlackNode node) {
if (node == null) {
return;
}
System.out.println("key: " + node.key
+ ", value: " + node.value
+ ", color: " + node.color
+ ", parent: " + (node.parent == null ? "null" : node.parent.key));
print(node.left);
print(node.right);
}
}
数据结构
算法
程序员内功
- 作者：lzlg520
- 发表时间：2023-09-13 21:43
- 版权声明：自由转载-非商用-非衍生-保持署名
- 公众号转载：请在文末添加作者公众号二维码
