算法训练-数据结构
·
类型：数组+移位/排序
1.数组元素循环左移p位后的结果。
循环左移和以下操作等价：
1.通过中间元素对称翻转
2.将数组分为n-p个和p个两部分
3.分别翻转这两个数组即可
// 中心翻转
void Reverse(int R[], int left, int right) {
while (left < right) {
int temp = R[left];
R[left] = R[right];
R[right] = temp;
left++;
right--;
}
}
//分组再翻转
void CyclicLeftShift(int R[], int n, int p) {
Reverse(R, 0, n-1); // 全部逆置
Reverse(R, 0, p-1); // 前p个逆置
Reverse(R, p, n-1); // 后n-p个逆置
}
2.两个整数递增有序序列A，B分别有n和m个元素，求第K大的数（1≤k≤n+m），要求算法有最佳时间复杂度
例子：输入A={1,3,4,5,6}，B={3,4,5,6}，K=4
思路：
A、B递增，从大到小数到第k个即可。（时间复杂度o(k)）
public class KthLargestInTwoArrays {
/**
* 方法1：双指针合并 - 时间复杂度O(K)，空间复杂度O(1)
*/
public static int findKthLargest1(int[] A, int[] B, int k) {
int n = A.length, m = B.length;
int i = n - 1, j = m - 1; // 从后往前遍历（因为要求第K大）
int count = 0;
int result = 0;
// 两个数组都还没数完的情况
while (i >= 0 && j >= 0) {
count++;
if (A[i] >= B[j]) {
if (count == k) return A[i];
i--;
} else {
if (count == k) return B[j];
j--;
}
}
// 如果其中一个数组遍历完
while (i >= 0) {
count++;
if (count == k) return A[i];
i--;
}
while (j >= 0) {
count++;
if (count == k) return B[j];
j--;
}
return -1; // k超出范围
}
}
类型：数学
3. 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
思路：
相当于一个减法运算，得到最大差值。
所以找到最大的被减数和最小的减数即可。
public class StockProfit {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
//初始值-最低价格，遇到最低价格则更新
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
// 更新最低价格
if (prices[i] < minPrice) {
minPrice = prices[i];
}else if (prices[i] - minPrice > maxProfit) {
// 计算当前价格卖出能获得的利润，更新最大利润
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
}
类型 ：数组+双指针
4. 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
思路：
- 相当于求出宽*高,也就是（b-a）*min(b,a)的最大值。乘数越大越好
- 只需更换a,b的值就好,更换条件，比min(b,a)大则更换，否则不换
public class Solution {
public int maxArea(int[] height) {
int left = 0; // 左指针
int right = height.length - 1; // 右指针
int maxArea = 0; // 最大面积
while (left < right) {
// 计算当前容器的面积
int currentWidth = right - left;
int currentHeight = Math.min(height[left], height[right]);
int currentArea = currentWidth * currentHeight;
// 更新最大面积
maxArea = Math.max(maxArea, currentArea);
// 移动较短的指针，希望找到更高的垂线
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
类型：列表 + 堆 遍历
5. 有 k 个 非递减排列 的整数列表。找到一个最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
思路：
1.先随机取每个子列表的一个元素，存放在最小堆中，找出最大值和最小值组成区间
2.取出最小值，依次存入子列表的一个新值，更新最小区间
public int[] smallestRange(List<List<Integer>> nums) {
// 最小堆，存储三元组[元素值, 列表索引, 元素在列表中的索引]
// 堆按照元素值进行排序，最小的元素在堆顶
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int currentMax = Integer.MIN_VALUE; // 记录当前堆中所有元素的最大值
int k = nums.size(); // 列表的数量
// 初始化堆：将每个列表的第一个元素加入堆中
for (int i = 0; i < k; i++) {
// 检查当前列表是否为空
if (!nums.get(i).isEmpty()) {
int val = nums.get(i).get(0); // 获取当前列表的第一个元素
// 将三元组[元素值, 列表索引, 元素索引]加入堆
minHeap.offer(new int[]{val, i, 0});
// 更新当前最大值
currentMax = Math.max(currentMax, val);
}
}
// 初始化最小区间的起点和终点，设置为一个非常大的范围
int start = -1000000, end = 1000000;
int minRange = end - start; // 初始化最小区间长度
// 当堆中有k个元素时继续处理（确保每个列表至少有一个元素在考虑范围内）
while (minHeap.size() == k) {
// 从堆中取出当前最小的元素
int[] current = minHeap.poll();
int currentVal = current[0]; // 最小元素的值
int listIdx = current[1]; // 当前元素所在的列表索引
int elementIdx = current[2]; // 当前元素在列表中的索引
// 检查当前区间[currentVal, currentMax]是否比之前记录的最小区间更小
// 或者区间长度相同但起点更小（题目要求返回最小的区间）
if (currentMax - currentVal < minRange ||
(currentMax - currentVal == minRange && currentVal < start)) {
// 更新最小区间信息
minRange = currentMax - currentVal;
start = currentVal;
end = currentMax;
}
// 如果当前元素所在的列表还有下一个元素
if (elementIdx + 1 < nums.get(listIdx).size()) {
// 获取下一个元素的值
int nextVal = nums.get(listIdx).get(elementIdx + 1);
// 将下一个元素加入堆中
minHeap.offer(new int[]{nextVal, listIdx, elementIdx + 1});
// 更新当前最大值（因为新加入的元素可能比当前最大值更大）
currentMax = Math.max(currentMax, nextVal);
} else {
// 如果当前列表已经遍历完，则退出循环
// 因为无法保证每个列表至少有一个元素在区间内了
break;
}
}
// 返回找到的最小区间
return new int[]{start, end};
}
main(){
Solution solution = new Solution();
// 创建测试数据
List<List<Integer>> nums = new ArrayList<>();
nums.add(Arrays.asList(4, 10, 15, 24, 26));
nums.add(Arrays.asList(0, 9, 12, 20));
nums.add(Arrays.asList(5, 18, 22, 30));
// 调用方法并输出结果
int[] result = solution.smallestRange(nums);
}
DFS深度遍历
6.给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。假设该网格的四条边均被水包围。
思路：计算不连通无向图的个数
public class Island {
// DFS
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
// 定义岛屿的数量/几行/几列
int count = 0;
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 发现新的岛屿
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
// 边界检查
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}
// 将当前陆地标记为已访问（改为水）
grid[i][j] = '0';
// 递归访问四个方向
dfs(grid, i - 1, j); // 上
dfs(grid, i + 1, j); // 下
dfs(grid, i, j - 1); // 左
dfs(grid, i, j + 1); // 右
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '1', '0'},
{'1', '1', '0', '1'},
{'1', '1', '1', '1'},
{'0', '1', '1', '0'}
};
System.out.println(new Island().numIslands(grid));
}
}
遍历路径如下：先红色路径到底，再绿色路径到底
拓扑排序
7.你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a, b] ，表示如果要学习课程 ai则 必须 先学习课程 b。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
思路：计算所有不连通有向图的节点总个数，用邻接表+拓扑图计算。
图结构：
顶点：课程（0到numCourses-1）
边：先修关系，如[ai, bi]表示从bi指向ai的有向边
邻接表：存储每个顶点的出边（指向的课程）
import java.util.ArrayList;
import java.util.*;
public class Course {
// 空间上：1.存储课程依赖关系的邻接表 2.每门课程的入度 3.当前可以学习的课程队列
// 关系：取出入度为0的数据，根据入度为0的依赖关系取出对应的课程，取出并计数，更新课程入度。循环
public boolean isFinish(int numCourses,int[][] prerequisites) {
// 1. 创建邻接表--存储课程之间的依赖关系
List<List<Integer>> adjList = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
adjList.add(new ArrayList<>());
}
// 输出adjList
System.out.println("adjList: " + adjList.toString());
// 2.创建入度数组-记录每门课程还需要多少先修课程
int[] inDegree = new int[numCourses];
System.out.println("入度数组: ");
System.out.println(Arrays.toString(inDegree) );
// 3.填充邻接表和入度数组
for(int[] prereq: prerequisites) {
int course = prereq[0];
int pre = prereq[1];
// 添加每个课程依赖的课程(邻接关系)
adjList.get(pre).add(course);
//每个课程顶点的入度
inDegree[course]++;
}
//
System.out.println("adjList: " + adjList.toString());
System.out.println("入度数组: ");
System.out.println(Arrays.toString(inDegree) );
// 4. 初始化队列（添加所有入度为0的节点）-存储当前可以学习的课程
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
// 向队列中添加元素
queue.offer(i);
}
}
System.out.println("可以学习的课程: " + queue.toString());
// 5. 拓扑排序
int count = 0;
while (!queue.isEmpty()) {
// 从队列头部移除并返回元素--从队列中取出课程学习
int current = queue.poll();
count++;
// 遍历当前节点的所有邻居---将入度变为0的课程加入队列
for (int neighbor : adjList.get(current)) {
// 更新该课程所有后继课程的入度
inDegree[neighbor]--;
System.out.println("更新后的入度："+Arrays.toString(inDegree) );
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
System.out.println("可以学习的课程: " + queue.toString());
}
}
}
// 6. 检查是否所有课程都能完成
return count == numCourses;
}
public static void main(String[] args) {
Course solution = new Course();
// 创建依赖图
int numCourses = 8;
int[][] prerequisites = {
{1, 0}, {2, 0}, {3, 1}, {3, 2},
{4, 3}, {5, 3}, {6, 4}, {6, 5},
{7, 6}
};
System.out.println(
"是否可以完成："+ solution.isFinish(numCourses, prerequisites)
);
}
}
8.给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路：因为链表是单方向的，所以使用双指针，第一个指针先从头节点走n步，然后第二个指针开始从头部向后走，同时，第一个指针继续向后直到结尾。第二个指针再进行删除操作即可（slow.next = slow.next.next）。
// 链表节点定义
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
// 辅助方法：打印链表
public static void printList(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println("null");
}
// 辅助方法：通过数组创建链表
public static ListNode createList(int[] arr) {
if (arr == null || arr.length == 0) return null;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
for (int num : arr) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
}
class LinkedListDemo {
// 方法一：双指针法（最优）
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// 快指针先走n+1步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 快慢指针同时前进
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 删除节点
slow.next = slow.next.next;
return dummy.next;
}
public static void main(String[] args) {
LinkedListDemo solution = new LinkedListDemo();
// 测试用例1
System.out.println("测试用例1:");
int[] arr1 = {1, 2, 3, 4, 5};
ListNode head1 = ListNode.createList(arr1);
System.out.print("原链表: ");
ListNode.printList(head1);
}
}
数组快速排序
9.给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路：第k大等价于第n-k+1小，通过快速排序法解决问题。
快速排序法过程：
1.随机取数组中一个元素作为基准元素，比它小的放左边，比它大的放右边
2.判断基准元素的下标，相等则结束，若小于n-k，则在其右边部分继续执行步骤1，否则在左边
3.直到找到第n-k+1小的元素的下标
import java.util.Random;
class MaxEle{
private Random random = new Random;
/**
* 快速选择算法：在数组nums[left...right]中寻找第k小的元素
* @param nums 数组
* @param left 当前搜索范围的左边界
* @param right 当前搜索范围的右边界
* @param kSmallest 要寻找的第k小的索引位置（0-based）
* @return nums中第k小的元素值
*/
private int quickSelect(int[] nums,int left,int right,int k){
if(left == right){
return nums[left];
}
// 随机选择基准元素索引
int pivotIndex = left + random.nextInt(right-left+1);
// 返回基准元素的位置
pivotIndex = partition(nums,left,right,pivotIndex);
// 3. 根据基准元素位置决定下一步搜索方向
if (kSmallest == pivotIndex) {
// 基准元素正好是第k小的元素
return nums[kSmallest];
} else if (kSmallest < pivotIndex) {
// 第k小的元素在基准元素的左侧，继续在左半部分搜索
return quickSelect(nums, left, pivotIndex - 1, kSmallest);
} else {
// 第k小的元素在基准元素的右侧，继续在右半部分搜索
return quickSelect(nums, pivotIndex + 1, right, kSmallest);
}
}
/**
* 分区操作：将数组重新排列，使得所有小于基准的元素在基准左侧，
* 所有大于等于基准的元素在基准右侧
*
* @param nums 数组
* @param left 当前分区范围的左边界
* @param right 当前分区范围的右边界
* @param pivotIndex 选择的基准元素的初始索引
* @return 基准元素在分区后的最终索引位置
*/
private int partition(int[] nums, int left, int right, int pivotIndex) {
// 1. 保存基准元素的值
int pivotValue = nums[pivotIndex];
// 2. 将基准元素交换到当前范围的最后位置（right索引处）
// 这样我们可以从左到右扫描，将小于基准的元素移到左侧
swap(nums, pivotIndex, right);
// 3. storeIndex指针：指向下一个小于基准的元素应该放置的位置
int storeIndex = left;
// 4. 扫描整个范围（除了最后的基准元素）
for (int i = left; i < right; i++) {
if (nums[i] < pivotValue) {
// 当前元素小于基准，将其交换到storeIndex位置
swap(nums, storeIndex, i);
storeIndex++; // 移动指针，指向下一个位置
}
}
// 5. 将基准元素从最后位置交换到它正确的位置（storeIndex）
// 此时，storeIndex左侧的所有元素都小于基准值
swap(nums, storeIndex, right);
// 6. 返回基准元素的最终位置
return storeIndex;
}
/**
* 交换数组中两个位置的元素
* @param nums 数组
* @param i 第一个索引
* @param j 第二个索引
*/
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int findKthLargest(int[] nums, int k) {
// 将问题转化为寻找第(n-k+1)小的元素（从小到大排序）
// 因为第k大 = 第(n-k+1)小（数组长度n）
// 这里使用0-based索引，所以是nums.length - k
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
// 测试
public static void main(String[] args) {
MaxEle maxEle = new MaxEle();
int[] nums = new int[10];
for (int i = 0; i < 10; i++) {
nums[i] = i;
}
System.out.println(maxEle.findKthLargest(nums, 6));
}
}
链表归并排序
10.给你链表的头结点 head ，将其按升序排列并返 排序后的链表 。
对于链表的归并排序，思路如下：
- 找到链表的中点，将链表拆分成两个子链表。
- 对两个子链表分别进行排序。
- 将两个排序后的子链表合并。
时间复杂度O(nlogn)：
分割：对于一个长度为 n 的序列，分割的次数为 log₂ n（以2为底的对数）
合并：合并时每一层遍历的次数为n
class Soluton{
public:
ListNode* sortList(ListNode* head){
// 节点为空或单个节点则终止
if(!head || !head->next) return head;
ListNode *slow = head,*fast = head->next;
// 找到中点
while(fast&&fast->next){
slow = slow->next;
fast = fast->next->next;
}
// 分割链表为两部分
ListNode *mid = slow->next;
slow->next = nullptr;
// 递归排序左右两部分
ListNode *left = sortList(head);
ListNode *right = sortList(head);
return merge(left,right);
}
private:
// 合并有序链表
ListNode* merge(ListNode* l1,listNode *L2){
List dummy(0);
listNode *tail = &dummy;
while(l1&&l2){
if(l1->val <= l2->val){
tail->next = l1;
l1 = l1->next;
}else{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
//连接剩余部分
tail ->next = l1?l1:l2;
return dummy.next;
}
}
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, com.demos.ListNode next) { this.val = val; this.next = next; }
}
class LinkSort {
public ListNode sortList(ListNode head) {
// 递归终止条件
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针找到链表中点
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 分割链表
ListNode mid = slow.next;
slow.next = null;
// 递归排序左右两部分
ListNode left = sortList(head);
ListNode right = sortList(mid);
// 合并两个有序链表
System.out.println(left.val + " ," + right.val);
return merge(left, right);
}
// 合并两个有序链表
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
// 处理剩余节点
if (l1 != null) {
cur.next = l1;
} else {
cur.next = l2;
}
return dummy.next;
}
public static void main(String[] args) {
// 创建链表：4 -> 2 -> 1 -> 3
ListNode head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);
LinkSort solution = new LinkSort();
ListNode sorted = solution.sortList(head);
// 打印排序后的链表：1 -> 2 -> 3 -> 4
while (sorted != null) {
System.out.print(sorted.val + " ");
sorted = sorted.next;
}
}
}
根据遍历顺序递归构建树
11.根据先序排序和中序排序生成树并确定根元素
思路：
1.根据先序遍历顺序确定根元素
2.根据这个根元素在中序遍历中的位置分为左子树和右子树
3.分别遍历左子树和右子树，递归执行以上两步
import java.util.HashMap;
import java.util.Map;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
public class TreeGenerate {
private Map<Integer, Integer> inorderIndexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
// 构建中序遍历值到索引的映射，便于快速查找根节点位置
Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTreeHelper(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1, inorderMap);
}
// 递归构建二叉树的辅助函数
private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd,
Map<Integer, Integer> inorderMap) {
// 递归终止条件
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// 前序遍历的第一个元素是根节点
TreeNode root = new TreeNode(preorder[preStart]);
// 在中序遍历中找到根节点的位置
int rootIndex = inorderMap.get(root.val);
// 计算左子树的节点个数
int leftTreeSize = rootIndex - inStart;
// 递归构建左子树
// 左子树在前序遍历中的范围: [preStart + 1, preStart + leftTreeSize]
// 左子树在中序遍历中的范围: [inStart, rootIndex - 1]
root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
inorder, inStart, rootIndex - 1, inorderMap);
// 递归构建右子树
// 右子树在前序遍历中的范围: [preStart + leftTreeSize + 1, preEnd]
// 右子树在中序遍历中的范围: [rootIndex + 1, inEnd]
root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
inorder, rootIndex + 1, inEnd, inorderMap);
System.out.println(root.val);
// 递归最深的地方（叶子节点）会最先执行 return root
// 然后逐层向上返回
return root;
}
public static void main(String[] args) {
TreeGenerate treeGenerate = new TreeGenerate();
// 测试用例1: 标准二叉树
System.out.println("=== 测试用例1: 标准二叉树 ===");
int[] preorder1 = {3, 9, 20, 15, 7};
int[] inorder1 = {9, 3, 15, 20, 7};
TreeNode root1 = treeGenerate.buildTree(preorder1, inorder1);
System.out.println(root1.val);
}
}
求二叉搜索树中与给定数值差值最小的节点。
12. 计一个高效的算法来找到二叉搜索树中与给定值 k 差值绝对值最小的节点。
思路：
计算当前节点与k差值的绝对值
1.从根节点开始遍历并更新最小差值
2.若K<根元素，则遍历其左子树
3.若K>根元素，则遍历其右子树
4.若K = 根元素，则直接结束
typedef struct BinarySearchNode
{
int data;
struct BinarySearchNode* left;// 注意：这里不能写 BiTreeNode* left (在C语言中)
struct BinarySearchNode* right;
}BinarySearchNode;
typedef BinarySearchNode* BiTree;
void searchX(BiTree root, int k){
if(!root){
cout << "树为空！" << end1;
return;
}
BiTree current = root;//当前节点
BiTree bestNode = root;//最佳节点
int minDiff = abs(root->data - k);
while(current){
int currentDiff = abs(current->data -k);
// 更新最优解
if(currentDiff < minDiff){
minDiff = currentDiff;
bestNode = current;
}
// 如果找到完全相等的值，提前结束
if (currentDiff == 0) {
break;
}
// 根据BST特性决定搜索方向
if (k < current->data) {
current = current->left; // 只需要搜索左子树
} else {
current = current->right; // 只需要搜索右子树
}
}
cout << "与 k 差值绝对值最小的节点值: " << bestNode->data << endl;
cout << "最小绝对差值: " << minDiff << endl;
}
二叉树遍历
13.给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
思路：深度遍历或广度遍历（每层1个节点）
深度遍历：
1.创建列表容器，压入根节点
2.先遍历当前节点的右子树，若树的深度 等于 列表长度，则压入容器（深度优先）
3.再遍历当前节点的左子树，若树的深度 等于 列表长度，则压入容器
public class RightValues {
// 二叉树节点定义
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// DFS递归
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode node, int depth, List<Integer> res) {
if (node == null) return;
// 第一个访问的节点，depth=0
if (depth == res.size()) res.add(node.val);
// 先递归右子树，再递归左子树
dfs(node.right, depth + 1, res);
dfs(node.left, depth + 1, res);
}
public static void main(String[] args) {
// 构建测试二叉树
// 1
// / \
// 2 3
// \ \
// 5 4
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
RightValues solution = new RightValues();
// 测试BFS方法
List<Integer> result1 = solution.rightSideView(root);
System.out.println("BFS结果: " + result1);
}
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)