将有序数组转换为二叉搜索树package hot100; public class lc108 { /*108. 将有序数组转换为二叉搜索树 给你一个整数数组 nums 其中元素已经按 升序 排列 请你将其转换为一棵 平衡 二叉搜索树。*/ public TreeNode sortedArrayToBST(int[] nums) { TreeNode ans Build(nums,0, nums.length-1); return ans; } public TreeNode Build(int[] nums, int left, int right){ if(left right){ return null; } if(left right){ return new TreeNode(nums[left]); } int mid left (right - left)/2; TreeNode leftnode Build(nums, left, mid-1); TreeNode rightnode Build (nums, mid1,right); TreeNode node new TreeNode(nums[mid],leftnode, rightnode); return node; } // 中序遍历打印用于验证结果是否有序 public static void inorder(TreeNode root) { if (root null) return; inorder(root.left); System.out.print(root.val ); inorder(root.right); } // 主函数测试 public static void main(String[] args) { int[] nums {-10, -3, 0, 5, 9}; lc108 solution new lc108(); TreeNode root solution.sortedArrayToBST(nums); System.out.print(中序遍历结果); inorder(root); System.out.println(); // 换行 } }验证二叉搜索树package hot100; import java.util.*; public class lc98 { /*98. 验证二叉搜索树 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树只包含 严格小于 当前节点的数。 节点的右子树只包含 严格大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树*/ long pre Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { //栈 //integer数字不够 long pre Long.MIN_VALUE; DequeTreeNode stack new ArrayDeque(); while(!stack.isEmpty() || root ! null){ while(root! null){ stack.push(root); root root.left; } root stack.pop(); if(root.val pre){ return false; } pre root.val; root root.right; } return true; } public static void main(String[] args) { lc98 solution new lc98(); // 测试用例1: 有效的 BST // 2 // / \ // 1 3 TreeNode root1 new TreeNode(2, new TreeNode(1), new TreeNode(3)); System.out.println(测试1 (有效): solution.isValidBST(root1)); // 应输出 true // 测试用例2: 无效的 BST右子树中有小于根节点的值 // 5 // / \ // 1 4 // / \ // 3 6 TreeNode root2 new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)) ); System.out.println(测试2 (无效): solution.isValidBST(root2)); // 应输出 false // 测试用例3: 边界值只含一个节点 Integer.MIN_VALUE TreeNode root3 new TreeNode(Integer.MIN_VALUE); System.out.println(测试3 (边界): solution.isValidBST(root3)); // 应输出 true // 测试用例4: 空树null System.out.println(测试4 (空树): solution.isValidBST(null)); // 应输出 true } }叉搜索树中第 K 小的元素package hot100; import java.util.*; public class lc230 { /*230. 二叉搜索树中第 K 小的元素 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 小的元素k 从 1 开始计数。*/ public int kthSmallest(TreeNode root, int k) { DequeTreeNode stack new ArrayDeque(); int jishu 0; while(!stack.isEmpty() || root ! null){ while(root! null){ stack.push(root); root root.left; } root stack.pop(); jishu; if(jishu k){ return root.val; } root root.right; } return k; } // 主函数测试 public static void main(String[] args) { lc230 solution new lc230(); // 构造 BST: // 3 // / \ // 1 4 // \ // 2 TreeNode root new TreeNode(3); root.left new TreeNode(1); root.right new TreeNode(4); root.left.right new TreeNode(2); // 测试不同的 k 值 int k1 1; int k2 3; System.out.println(第 k1 小的元素: solution.kthSmallest(root, k1)); // 应输出 1 System.out.println(第 k2 小的元素: solution.kthSmallest(root, k2)); // 应输出 3 } }二叉树的右视图package hot100; import java.util.*; public class lc199 { /*199. 二叉树的右视图 给定一个二叉树的 根节点 root想象自己站在它的右侧 按照从顶部到底部的顺序返回从右侧所能看到的节点值。*/ public ListInteger rightSideView(TreeNode root) { //层次遍历 DequeTreeNode queue new ArrayDeque(); ListInteger ans new ArrayList(); if(root null){ return ans; } queue.offer(root); while(!queue.isEmpty()){ int size queue.size(); for(int i 0; i size; i){ TreeNode temp queue.poll(); if(i size-1){ ans.add(temp.val); } if(temp.left ! null){ queue.offer(temp.left); } if(temp.right ! null){ queue.offer(temp.right); } } } return ans; } // 主函数测试 public static void main(String[] args) { lc199 solution new lc199(); // 测试用例1: 普通二叉树 // 1 // / \ // 2 3 // \ \ // 5 4 TreeNode root1 new TreeNode(1); root1.left new TreeNode(2); root1.right new TreeNode(3); root1.left.right new TreeNode(5); root1.right.right new TreeNode(4); System.out.println(测试1: solution.rightSideView(root1)); // 预期 [1, 3, 4] // 测试用例2: 左斜树只有左孩子 // 1 // / // 2 // / // 3 TreeNode root2 new TreeNode(1); root2.left new TreeNode(2); root2.left.left new TreeNode(3); System.out.println(测试2: solution.rightSideView(root2)); // 预期 [1, 2, 3] // 测试用例3: 右斜树只有右孩子 // 1 // \ // 2 // \ // 3 TreeNode root3 new TreeNode(1); root3.right new TreeNode(2); root3.right.right new TreeNode(3); System.out.println(测试3: solution.rightSideView(root3)); // 预期 [1, 2, 3] // 测试用例4: 空树 System.out.println(测试4: solution.rightSideView(null)); // 预期 [] } }二叉树展开为链表package hot100; import java.util.*; public class lc114 { /* 叉树展开为链表 给你二叉树的根结点 root 请你将它展开为一个单链表 展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同*/ public void flatten(TreeNode root) { //前序--创建链表 ListTreeNode list new ArrayList(); DequeTreeNode stack new ArrayDeque(); while(!stack.isEmpty() || root ! null ){ while(root ! null){ list.add(root); stack.push(root); root root.left; } root stack.pop(); root root.right; } for(int i 1; i list.size(); i){ TreeNode pre list.get(i-1); TreeNode cur list.get(i); pre.left null; pre.right cur; } } // 辅助方法按前序遍历打印树用于验证结果 public static void printPreorder(TreeNode root) { if (root null) return; System.out.print(root.val ); printPreorder(root.left); printPreorder(root.right); } // 辅助方法打印展开后的链表只沿 right 走 public static void printList(TreeNode root) { TreeNode cur root; while (cur ! null) { System.out.print(cur.val ); // 验证 left 均为 null if (cur.left ! null) { System.out.print((left非空!) ); } cur cur.right; } System.out.println(); } public static void main(String[] args) { lc114 solution new lc114(); // 构造示例树: [1,2,5,3,4,null,6] TreeNode root new TreeNode(1); root.left new TreeNode(2); root.right new TreeNode(5); root.left.left new TreeNode(3); root.left.right new TreeNode(4); root.right.right new TreeNode(6); System.out.print(原始树前序遍历: ); printPreorder(root); System.out.println(); solution.flatten(root); System.out.print(展开后的链表 (只沿right): ); printList(root); // 预期结果: 1 2 3 4 5 6 } }碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第70天。努力连续更新100天以后每天就按秋招项目【java agent】科研必做项目算法八股锻炼身体来总结。总结下周开始java项目1.hot100 【acm】 46/100 2到3h快速把hot100过一遍【7/20】2.秋招项目【java 项目】【agent 项目 】继续3.科研。确定方向就搞就可以了4.实习6.背八股无7.锻炼身体无要点:坚持