林重笑

216.组合总和III文章：4. 组合总和III 题目：216. 组合总和 III 【思路】 二编：把i写成了startIndex 和77.组合相似的解法。 在写题目的过程中，经常把回溯函数的遍历起始索引写成startIndex，而我们需要写的是i。 startIndex是在同一个集合里面遍历，防止重复遍历 Java实现 1234567891011121314151617181920212223class Solution { List<List<Integer>>res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backtracking(k,n,1,0); return res; } public vo ...

回溯理论基础回溯法（回溯搜索法），是一种搜索的方式。 只要有递归就会有回溯。 因此，回溯函数也就是递归函数，指的都是一个函数。 回溯的本质是穷举。 回溯法解决的问题 组合问题：N个数里面按一定规则找出k个数的集合。 切割问题：一个字符串按一定规则有几种切割方式。 子集问题：一个N个数的集合里有多少个符合条件的子集。 排列问题：N个数按一定规则全排列，有几种排列方式。 棋盘问题：N皇后，解数独等等 排列？组合？ 组合是不强调元素顺序的，排列是强调元素顺序的。 组合无序，排列有序 如何理解回溯法回溯法解决的问题都可以抽象为树形结构。 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度都构成了树的深度。 回溯三部曲 回溯函数模板返回值以及参数 名字：backtracking 返回值：一般为void 参数：一般先写逻辑，然后需要什么参数就填什么参数 终止条件 一般来说搜到叶子节点也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。 回溯搜索的遍历过程 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度 1 ...

669.修建二叉树文章：31. 修剪二叉搜索树 题目：669. 修剪二叉搜索树 视频：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树_哔哩哔哩_bilibili 【常见误区】 不能直接return删除当前节点后的左右子树，有可能左右子树里面也有需要删除的节点。因此我们需要return的是当前函数（递归） Java实现 12345678910class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if(root == null)return root; if(root.val > high)return trimBST(root.left,low,high); if(root.val < low)return trimBST(root.right,low,high); root.left = trimBST(root.left,low,high); ...

235.二叉搜索树的最近公共祖先文章：28. 二叉搜索树的最近公共祖先 题目：235. 二叉搜索树的最近公共祖先 【思路】 二叉搜索树：找到一个节点的值在两边的子树、在p和q之间（一定是最近的公共祖先！） 搜索一条边的写法： 12if (递归函数(root->left)) return ;if (递归函数(root->right)) return ; 搜索整个树写法： 123left = 递归函数(root->left);right = 递归函数(root->right);left与right的逻辑处理; 本题只需要搜索一条边的写法，遇到递归函数的返回值，如果不为空则立即返回 Java实现 会出现乘积溢出的情况： 123if((root.val - p.val) * (root.val - q.val) <= 0){ return root; } 12345678910111213141516class Solution { public TreeNode lowest ...

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实现 123456789101112131415161718class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); int res =0; queue.add(root); while(!queue.isEmpty()){ int len = queue.size(); for(int i =0;i<len;i++){ TreeNo ...

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 ...

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 resList; } // ...