幻境

组合总和IIIlink：216. 组合总和 III - 力扣（LeetCode） 思路分析既然是要比对，那自然需要和目标值比对的sum，同时要记录path.这么一想其实和我们之前分析的组合问题就非常相似了.注意一下题目中给定的判定逻辑限制（数字1-9且不能重复）很完美的组合问题.天生的回溯搭子. 1234567891011121314151617181920212223242526272829303132333435class Solution { //记录路径 List<Integer> path = new LinkedList<>(); //记录结果 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backtracking(n,k,1,0); return ...

初探回溯什么是回溯算法回溯算法是一种暴力穷举的搜索方式.回溯和递归是相辅相承的**.(有递归就会有回溯)** 回溯法解决的问题 组合问题：N个数里面按一定规则找出k个数的集合. 切割问题：一个字符串按一定规则有几种切割方式. 子集问题：一个N个数的集合里有多少符合条件的子集. 排列问题：N个数按一定规则全排列，有几种排列方式. 棋盘问题：N皇后，解数独等. 使用回溯算法解决问题的思路虽然回溯算法暴力效率低下理解起来更为抽象，但好在天无绝人之路，回溯算法的问题都可以用树形结构来进行理解. 关键有以下两点：1.集合大小->树的宽度2.递归深度->树的深度 123456789101112void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 ...

修建二叉搜索树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) { * ...

二叉搜索树的最近公共祖先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 ...

验证二叉搜索树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 ...

最大二叉树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 = ...

找树左下角的值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) { * ...

二叉树的最大深度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 ...

二分查找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 ...

二叉树的层序遍历（广度优先遍历）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 ...