林重笑

235.二叉搜索树的最近公共祖先文章：28. 二叉搜索树的最近公共祖先 题目：235. 二叉搜索树的最近公共祖先 【思路】 二叉搜索树：找到一个节点的值在两边的子树、在p和q之间（一定是最近的公共祖先！） Java实现 会出现乘积溢出的情况： 123if((root.val - p.val) * (root.val - q.val) <= 0){ return root; } 12345678910111213141516class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(true){ if(root.val >p.val && root.val > q.val){ return lowestCommonAncest ...

530.二叉搜索树的最小绝对差文章：24. 二叉搜索树的最小绝对差 题目：530. 二叉搜索树的最小绝对差 【思路】 递归二叉搜索树中采用中序遍历，其实就是一个有序数组。 最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。 Java实现 1234567891011121314151617181920class Solution { int min = Integer.MAX_VALUE; TreeNode pre; public int getMinimumDifference(TreeNode root) { traversal(root); return min; } public void traversal(TreeNode node){ if(node == null)return ; traversal(node.left); if(pre!=null){ ...

654.最大二叉树文章：19. 最大二叉树 题目：654. 最大二叉树 视频：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili 【思路】 构造二叉树类型的题目，我们都使用前序遍历对二叉树进行构造。 先构造中间节点，再构造左子树，最构造右子树 递归 1.确递归函数的参数和返回值 2.确定终止条件 当传入的数组大小为1的时候，说明遍历到了叶子节点 那么应该定义一个新节点，把这个数组的数值赋给新的节点，然后返回这个节点。 3.确定单层递归的逻辑 先找到数组中最大值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。 最大值所在的下标左区间 构造左子树 最大值所在的下标右区间 构造右子树 Java实现 123456789101112131415161718class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return traversal(nums,0,nums.length); &# ...

513.找树左下角的值文章：16. 找树左下角的值 题目：513. 找树左下角的值 【思路】 用层序遍历，循环遍历获得每一层的第0位，最后赋值的即最后一层（左下角）的值。 Java实现 1234567891011121314151617class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int res = 0; while(!queue.isEmpty()){ int len = queue.size(); for(int i = 0;i<len;i++){//循环边缘找错了 TreeNode node = queue.poll(); if(i==0 ...

110.平衡二叉树（递归法）题目：110. 平衡二叉树 文章：12. 平衡二叉树 视频：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树_哔哩哔哩_bilibili 【思路】 平衡二叉数：任何节点的左右子树的高度差不超过1 高度？深度？ 高度：距离叶子节点的距离 后序遍历，层层向上返回高度+1 深度：距离根节点的距离 前序遍历，层次向下+1 采用后序遍历 Java实现 递归 12345678910111213141516171819class Solution { public boolean isBalanced(TreeNode root) { int result = getHeight(root); return result==-1?false:true; } public int getHeight(TreeNode root){ if(root == null)return 0; int leftHeight = get ...

222.完全二叉树的节点个数【思路】 普通二叉树：层序遍历后统计item的个数，累加即可。 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含1~2^(h-1)个节点。 避免了不必要的节点遍历，节省了时间 判断当前节点的子树是否为满二叉树：判断左右子树的深度是否相同，相同的话即满二叉树，用公式就可以算出满二叉树的节点了。 Java实现 普通二叉树解法（层序遍历） 1234567891011121314151617181920212223class Solution { public int countNodes(TreeNode root) { int num = 0; if(root == null)return num; Queue<TreeNode>queue = new LinkedList<TreeNode>(); queue.add(ro ...

二叉树层序遍历文章：5. 二叉树的层序遍历 层序遍历：广度搜索 102.二叉树的层序遍历题目：102. 二叉树的层序遍历 【思路】 层序遍历一个二叉树，就是用左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前见过的都不太一样。需要借助一个辅助数据结构，即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历，也就是递归的逻辑。 而这种层序遍历方式就是图论中的广度优先搜索，只不过是应用在了二叉树上。 Java实现 递归实现 1234567891011121314151617181920class Solution { public List<List<Integer>>resList = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(TreeNode root) { checkFunc(root,0); return resL ...

二叉树理论基础文章：1. 二叉树理论基础 视频：关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩_bilibili 种类满二叉树定义：如果一颗二叉树上只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。 深度为k，节点数：2^k-1 除了底层以外，从左到右其他地方都是满的，是完全二叉树 完全二叉树定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含 1 ~ 2^(h-1)个节点。 优先级队列->堆 是完全二叉树，同时保证父子节点的顺序关系。 二叉搜索树前面介绍的数都是没有数值的，而二叉搜索树是有数值的。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树 平衡二叉搜索树性质：它是一棵空树或它的左右两个子树的高度的绝对值不超过1，并且左右两个子 ...

239.滑动窗口最大值文章：7. 滑动窗口最大值 题目：239. 滑动窗口最大值 视频：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili 难点在于：如何求滑动窗口里面的最大值。 【思路】 滑动窗口很像一个队列。 单调队列。维护队列里面的元素单调递增或单调递减。 因此我们采用Deque进行处理：著需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。 1.pop(value)： 如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。 2.push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到（while）push元素的数值小于等于队列入口元素的数值为止。 保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。 pop() push() getMaxValue() Java实现 123456789101112131415161718192021222324252627282930313233 ...

哈希表常见的三种哈希结构：数组、set、map 当我们需要快速判断一个元素是否出现在集合里的时候，就考虑哈希法。 set可以去重 如果需要统计元素出现过多少次 && 去重 -> 使用map 【总结】 map虽然是万能的，但是我们也需要判断好什么时候用数组、什么时候用set。 双指针需要注意边界值，很容易造成越界。 三数之和 && 四数之和是很明显的使用双指针的题目，通过选取当前值的下一位向后遍历、选取最后的值向前遍历，完成对当前值的和进行扫描统计。同时，我们需要完成去重的逻辑 ： 一定要放在一个符合条件的结果下面，不然会导致当前结果无法写入结果集。 在四数之和中，我们还可以完成去重和剪枝的操作，但是需要判断好剪枝的条件是否完全正确。 字符串双指针法使用双指针完成对字符串位置交换（逆序排序）的操作。 KMP算法解决：字符串匹配问题 找不匹配字符的前一位的最长相等前后缀的下一位（相当于节省了重头开始遍历、从前面前后缀相同的下一位开始重新寻找） 1.1通过模式串来初始化前缀表（next表） 1.2.处理前后缀不相同 1.3.处理前后缀相同 2.使用ne ...