108. 将有序数组转换为二叉搜索树
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {// 输入一个有序数组，将其转换为高度平衡的二叉搜索树public TreeNode sortedArrayToBST(int[] nums) {// 调用辅助函数，从数组的最左边到最右边构建树TreeNode node = helper(nums, 0, nums.length - 1);// 返回构建的树的根节点return node;}// 辅助函数，使用中序遍历构建平衡的二叉搜索树private TreeNode helper(int[] nums, int left, int right) {// 基本情况：如果左指针大于右指针，返回 nullif (left > right) {return null;}// 计算中间索引int mid = (left + right) / 2;// 创建树节点，以中间值为根TreeNode root = new TreeNode(nums[mid]);// 递归处理左半部分，构建左子树root.left = helper(nums, left, mid - 1);// 递归处理右半部分，构建右子树root.right = helper(nums, mid + 1, right);// 返回当前节点return root;}}
148. 排序链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 对链表进行排序，返回排序后的链表头节点public ListNode sortList(ListNode head) {ListNode tmp = head; // 创建一个临时指针 tmp，初始指向链表头List<Integer> arr = new ArrayList<>(); // 创建一个列表，用于存储链表节点的值// 1. 遍历链表，将每个节点的值存入数组while (tmp != null) {arr.add(tmp.val); // 将当前节点的值添加到列表中tmp = tmp.next; // 移动到下一个节点}// 2. 对列表进行排序Collections.sort(arr); // 使用 Collections.sort 方法对列表进行排序// 3. 将排序后的值重新赋给链表中的节点int i; // 索引变量for (i = 0, tmp = head; i < arr.size() && tmp != null; i++, tmp = tmp.next) {tmp.val = arr.get(i); // 将排序后的值重新赋给链表的节点}// 4. 返回排序后的链表头节点return head; // 返回头节点，链表已按升序排序}
}
427. 建立四叉树
class Solution {// 主方法，接受一个二维数组public Node construct(int[][] grid) {// 从 (0, 0) 开始构建，网格的大小return dfs(grid, 0, 0, grid.length, grid.length);}// 深度优先搜索（DFS）方法，构建四叉树public Node dfs(int[][] grid, int r0, int c0, int r1, int c1) {boolean same = true; // 判断当前矩形区域内的值是否相同// 检查从 (r0, c0) 到 (r1, c1) 矩形区域中的每一个值for (int i = r0; i < r1; ++i) {for (int j = c0; j < c1; ++j) {// 如果存在与左上角不同的值，标记为不同if (grid[i][j] != grid[r0][c0]) {same = false; // 切换标志break; // 退出内层循环}}if (!same) {break; // 退出外层循环}}// 如果所有值相同if (same) {// 创建一个叶子节点，值为当前区域左上角的值return new Node(grid[r0][c0] == 1, true);}// 如果有不同的值，递归构建四个子节点Node ret = new Node(true, // 不是叶子节点false, // 为 false 表示非叶子节点dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2), // 左上子节点dfs(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1), // 右上子节点dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2), // 左下子节点dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1) // 右下子节点);return ret; // 返回构建好的节点}
}
