yubのAlgorithm.0x16
修建二叉搜索树link：669. 修剪二叉搜索树 - 力扣（LeetCode）
思路分析注意修剪的时候要考虑到全部的节点，即搜到到限定区间小于左值或者大于右值时还需要检查当前不符合区间大小节点的右子树/左子树，不能直接返回null.剪去节点只需要在判断当前节点左/右子树后将root的左/右节点更新即可.
递归12345678910111213141516171819202122232425262728293031/** * 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) { * ...
yubのAlgorithm.0x15.
二叉搜索树的最近公共祖先link：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
思路分析题目给出的是二叉搜索树，那就方便很多.（不用在意遍历顺序）已知左子树的值都比根节点小，右子树的值都比根节点大（每层都符合该规律）但是由于不知道p、q的值哪个比根节点大所以需要进行比较.我们在递归的时候只需要不断缩小判断区间即可.怎么缩小呢？和p、q的值进行比较即可.
递归1234567891011121314151617181920212223242526272829303132333435/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode lowestCommonAncestor(T ...
yubのAlgorithm.0x14
验证二叉搜索树link：98. 验证二叉搜索树 - 力扣（LeetCode）
思路分析搞清二叉搜索树的定义即可.(根节点的左子树比根节点小，右子树比根节点大且每个子树都满足)
但其实上述思路是是不对， 跑一下代码发现测试样例值通过了一部分.那是哪里出问题了？（烧烤）比较的应该是左子树所有节点小于中间节点，右子树所有节点大于中间节点.查资料发现二叉搜索树也可以为空
迭代1234567891011121314151617181920212223242526272829/** * 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 righ ...
yubのAlgorithm.0x13
最大二叉树link：654. 最大二叉树 - 力扣（LeetCode）
思路分析在数组中遍历找到最大值（根节点），分割得到左右子树，再回溯遍历左右子树（还是先找到最大值作为子树的根节点再遍历）
递归12345678910111213141516171819202122232425262728293031323334353637383940414243/** * 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 = ...
yubのAlgorithm.0x12
找树左下角的值link：513. 找树左下角的值 - 力扣（LeetCode）
思路分析看题目给出的样例分析，觉得可以从深度入手.如果是左子树深度最大，那直接输出最左边的左子树节点即可（只有一个左节点的话也是如出一辙）又假设二叉树中至少有一个节点，就已经列举出一种特殊需要判断的情况了.
递归12345678910111213141516171819202122232425262728293031323334353637383940414243/** * 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) { * ...
yubのAlgorithm.0x11
二叉树的最大深度link：104. 二叉树的最大深度 - 力扣（LeetCode）
思路分析高度：后序遍历深度：前序遍历但是其实这里我们可以选择后序遍历，根节点的高度就是树的深度.
递归1234567891011121314151617181920212223242526272829/** * 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 = righ ...
yubのAlgorithm.0x1
二分查找link：704. 二分查找 - 力扣（LeetCode）
思路分析题目给出数组升序 ，想到二分查找（好吧其实题目也给出来了w）找到mid，根据逻辑大小缩小范围比较.
全包围[lefg,right]假如数组大小为6，取值范围就是[0,5].闭区间使得定义left = 0，right = nums.length-1（防止越界指针无效，也是根据此处可以反推没有左开右闭情况）left指针是0.right是5，这个时候left == right是有效的，结束条件也就是left<=right，再根据mid位置进行判断，target是再mid左边还是右边或者是幸运的查找到目标位置.
123456789101112131415161718192021class Solution { public int search(int[] nums, int target) { //看到数组习惯性反应越界问题 //闭区间 int right = num ...
yubのAlgorithm.0x10
二叉树的层序遍历（广度优先遍历）link：102. 二叉树的层序遍历 - 力扣（LeetCode）
思路分析题目说明从左往右进行遍历，其实可以堪称给二叉树每一层都画横线分割开来，left first，right last.
n代表null 输出只从存在的节点中输出.最先想到的就是递归，按照创建树的思路，pass掉空节点就好.先前做过队列模拟栈，其实这里用队列来解决也很优雅.
队列BFS12345678910111213141516171819202122232425262728293031323334353637383940414243/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode ...
yubのAlgorithm.0x2
移除元素link：27. 移除元素 - 力扣（LeetCode）
思路分析1.常规遍历数组，比较vaule值是否相等，若不相等往前拷贝覆盖即可，相等跳过，更新下标（可以理解为数组长度减少）.【时间复杂度O(n) 空间复杂度O(1)】2.快慢指针.快指针遍历进行筛选，慢指针对应常见存储的数组.找到目标vaule后fast和slow指针拉开距离开始遍历维护更新.【时间复杂度O(n) 空间复杂度O(1)】
拷贝覆盖123456789101112class Solution { public int removeElement(int[] nums, int val) { int k = 0; for(int num:nums){ if(num != val){ nums[k] = num; k++; } } return k; }&# ...
yubのAlgorithm.0x3
有序数组的平方link：977. 有序数组的平方 - 力扣（LeetCode）非递减顺序一个数列中的元素从左到右依次不减，或者说不降序排列.比如：1233445，12345.
思路分析如果看到数组能条件反射到双指针那已经是win了.根据题意平方之后的数一定在数组的两端.两个指针一首一尾，从后往前更新数组.
1234567891011121314151617181920class Solution { public int[] sortedSquares(int[] nums) { //非递减数组可得最大值平方后会出现在数组两头 int left = 0; int right = nums.length - 1; int[] result = new int[nums.length]; int index = result.length - 1 ; while(left <= right) { if(nums[left]*nums[left] > nums[right ...
