说明方法不一定为最优但是思路都正确且基本可以跑通。第二十七题 二叉树的中序遍历利用栈将当前节点的左子树不断压栈然后出栈访问节点并转向当前节点的右子树/** * 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 right; * } * } */ class Solution { public ListInteger inorderTraversal(TreeNode root) { DequeTreeNode stack new ArrayDeque(); ListInteger listnew ArrayList(); TreeNode curroot; while(!stack.isEmpty()||cur!null){ while(cur!null){ stack.push(cur); curcur.left; } curstack.pop(); list.add(cur.val); curcur.right; } return list; } }第二十八题 二叉树的最大深度利用递归每层要做的只是调用自身函数并选出较大的字树层数1返回/** * 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 right; * } * } */ class Solution { public int maxDepth(TreeNode root) { TreeNode curroot; if(curnull){ return 0; } return Math.max(maxDepth(cur.left),maxDepth(cur.right))1; } }第二十九题 反转二叉树利用递归每层要做的就是反转自己的两个子树然后递归调用左子树反转右子树反转。如果当前叶子为空则返回空/** * 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 right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if(rootnull){ return root; } TreeNode cur root; TreeNode nodecur.left; root.leftroot.right; root.rightnode; if(root.left!null){ invertTree(root.left); } if(root.right!null){ invertTree(root.right); } return root; } }第三十题 对称二叉树树对称意味着树的left-leftright-right且left-rightright-left。因此对于每层只需要递归查看上述条件是否满足即可/** * 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 right; * } * } */ class Solution { public boolean isSymmetric(TreeNode root) { //树为空 if(rootnull) return false; //调用递归函数 return isMirror(root.left, root.right); } public boolean isMirror(TreeNode left, TreeNode right){ //如果两侧都是空返回true if(leftnullrightnull) return true; //有一侧不为空或者值不等返回false if(leftnull||rightnull) return false; if(left.val!right.val) return false; //递归调用查看是否left-leftright-right且left-rightright-left return isMirror(left.left, right.right)isMirror(left.right, right.left); } }第三十一题 二叉树的直径通过递归遍历所有节点对节点实行函数返回左右子树中深度较大的那个同时更新ans为max(左右子树深度和2左右子树中较深的深度1。最后返回ans和根节点函数返回这两个数据中较大的那个/** * 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 right; * } * } */ class Solution { //初始化ans因为可能最大直径不过根节点而递归函数只能计算经过当前节点的最大直径 public int ans0; public int diameterOfBinaryTree(TreeNode root) { //比较ans和最大直径 return Math.max(maxEdge(root), ans); } //计算经过当前节点的最大直径 public int maxEdge(TreeNode node){ //如果节点为空返回-1 if(nodenull){ return -1; } //递归调用得到左子树和右子树的最大直径 int leftmaxEdge(node.left); int rightmaxEdge(node.right); //更新ans即更新可能不经过根节点的最大直径 ansMath.max(Math.max(leftright2, Math.max(left, right)1), ans); //返回最大直径 return Math.max(left,right)1; } }第三十二题 二叉树的层序遍历层序遍历很简单通过队列就可以完成。具体思路是压入头节点取出头节点压入left和right。配合节点列表用于压队列和取队列配合数字列表进行结果列表的添加鉴于题目要求对每层进行分割因此需要创建整形列表用于添加到res创建节点列表用于遍历记得Dequeue可以用作栈pushpop也可以用作队列offerpoll/** * 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 right; * } * } */ class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger resListnew ArrayList(); TreeNode curroot; DequeTreeNode queuenew ArrayDeque(); //特殊情况判定 if(rootnull){ return resList; } //压入顶部 queue.offer(cur); //循环 while(!queue.isEmpty()){ //创建整形列表用于添加到res创建节点列表用于遍历 ListTreeNode listNodenew ArrayList(); ListInteger listNumnew ArrayList(); //将栈中的元素树的一层全部取出并加入到两个列表 while(!queue.isEmpty()){ curqueue.poll(); listNode.add(cur); listNum.add(cur.val); } //将整形列表加入到res resList.add(listNum); //通过节点列表取出下一层的全部节点放入队列 for(int i0;ilistNode.size();i){ if(listNode.get(i).left!null) queue.offer(listNode.get(i).left); if(listNode.get(i).right!null) queue.offer(listNode.get(i).right); } } return resList; } }第三十三题 将有序数组转换为二叉搜索树利用递归每次构造根节点的左子树和右子树/** * 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 right; * } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length-1); } //递归函数 public TreeNode build(int[] nums, int left, int right){ //如果左大于右则返回空节点 if(leftright){ return null; } //构造当前根节点并递归调用函数构造左子树和右子树 return new TreeNode(nums[(leftright)/2], build(nums, left, (leftright)/2-1), build(nums, (leftright)/21, right)); } }第三十四题 验证二叉搜索树每个节点都有一个合法的取值范围节点的val应该在min-max之间利用递归函数进行中序遍历检查每个节点是否在合法区间内/** * 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 right; * } * } */ class Solution { long prev Long.MIN_VALUE; public boolean isValidBST(TreeNode root) {、 将合法区间设置为最大和最小 return check(Long.MIN_VALUE, Long.MAX_VALUE, root); } public boolean check(Long min, Long max, TreeNode root){ //如果为空表明已经是底部直接返回true if(rootnull) return true; long valroot.val; //中序检查 先检查左子树 if(check(min, val, root.left)false) return false; //中序检查检查当前节点 if(root.valmin||root.valmax) return false; //中序检查检查右子树 if(check(val, max, root.right)true) return true; return false; } }第三十五题 二叉搜索树中第k小的元素遍历二叉树把每个节点值存于列表然后排序列表取出第k小的元素/** * 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 right; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { TreeNode curroot; DequeTreeNode queuenew ArrayDeque(); ListInteger listnew ArrayList(); queue.offer(cur); while(!queue.isEmpty()){ curqueue.poll(); list.add(cur.val); if(cur.left!null) queue.offer(cur.left); if(cur.right!null) queue.offer(cur.right); } list.sort(null); return list.get(k-1); } }第三十六题 二叉树的右视图层序遍历二叉树对于每一层只保留最后一个节点/** * 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 right; * } * } */ class Solution { public ListInteger rightSideView(TreeNode root) { //创建队列 DequeTreeNode queuenew ArrayDeque(); TreeNode curroot; //返回列表 ListInteger listRetnew ArrayList(); //特殊情况 if(rootnull){ return listRet; } //将根节点入队 queue.offer(cur); //层序遍历将一整层存于列表 while(!queue.isEmpty()){ ListTreeNode listnew ArrayList(); while(!queue.isEmpty()){ curqueue.poll(); list.add(cur); } //取出一层中最右侧的元素 listRet.add(list.get(list.size()-1).val); //将下一层的所有元素入队 for(int i0;ilist.size();i){ if(list.get(i).left!null) queue.offer(list.get(i).left); if(list.get(i).right!null) queue.offer(list.get(i).right); } } return listRet; } }第三十七题 二叉树展开为链表先前序遍历二叉树存于列表然后遍历列表修改指针即可/** * 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 right; * } * } */ class Solution { public void flatten(TreeNode root) { ListTreeNode listnew ArrayList(); visit(root, list); //修改指针 for(int i0;ilist.size()-1;i){ list.get(i).leftnull; list.get(i).rightlist.get(i1); } } //中序遍历 public ListTreeNode visit(TreeNode root, ListTreeNode list){ if(rootnull){ return list; } list.add(root); if(root.left!null) visit(root.left, list); if(root.right!null) visit(root.right, list); return list; } }第三十八题 从前序遍历和中序遍历构造二叉树从前序的第一个元素找到根节点在中序中找到根节点就能确定左子树和右子树的节点范围递归地构建左右子树/** * 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 right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder null || inorder null || preorder.length 0 || inorder.length 0) { return null; } if(inorder.length1) return new TreeNode(inorder[0]); if(preorder.length1) return new TreeNode(preorder[0]); int index0; for (int i0;iinorder.length;i) { if (inorder[i]preorder[0]) { indexi; break; } } int[] leftPreorderArrays.copyOfRange(preorder, 1, index1); int[] rightPreorderArrays.copyOfRange(preorder, index1, preorder.length); int[] leftInorderArrays.copyOfRange(inorder, 0, index); int[] rightInorderArrays.copyOfRange(inorder, index1, inorder.length); TreeNode curnew TreeNode(preorder[0], buildTree(leftPreorder, leftInorder), buildTree(rightPreorder, rightInorder)); return cur; } }第三十九题 路径总和III双重递归第一层递归遍历每个节点第二层递归判断每个节点之下的子树是否存在包含该节点的路径/** * 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 right; * } * } */ class Solution { public int pathSum(TreeNode root, long targetSum) { int ret0; if(rootnull) return 0; ret rootSum(root, targetSum); //因为rootSum函数限制需要遍历所有节点作为根节点查看是否有包含子树根节点的路径 ret pathSum(root.left, targetSum); ret pathSum(root.right, targetSum); return ret; } //这个函数只能查看在这个子树上是否有包含根节点的路径如果路径不包含根节点检测不到。 public int rootSum(TreeNode cur, long targetSum){ int cnt0; if(curnull) return 0; if(cur.valtargetSum) cnt; cntrootSum(cur.left, targetSum-cur.val); cntrootSum(cur.right, targetSum-cur.val); return cnt; } }第四十题 二叉树的最近公共祖先如果当前节点是p或q直接返回该节点可能是最近公共祖先递归在左右子树中查找p和q根据左右子树的返回结果判断左右都返回null → 当前子树没有p或q左右都返回非null → p和q分布在两侧当前节点就是最近公共祖先单侧返回非null → 将结果向上传递简单说就是谁先找到p或q就返回谁如果左右各找到一个当前节点就是答案。/** * 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(TreeNode root, TreeNode p, TreeNode q) { TreeNode curroot; return search(root, p, q); } public TreeNode search(TreeNode cur, TreeNode p, TreeNode q){ if(curnull) return null; if(curp||curq) return cur; TreeNode leftRessearch(cur.left, p, q); TreeNode rightRessearch(cur.right, p, q); //子树中没有p或q if(leftResnullrightResnull){ return null; //自己为最近公共祖先 }else if(leftRes!nullrightRes!null){ return cur; }else{ //子树中包含p或q if(leftRes!null){ return leftRes; }else{ return rightRes; } } } }第四十一题 岛屿数量遍历整个网格找到陆地1每找到一块新的陆地岛屿数1用DFS把这块岛屿全部淹没变成0避免重复计数class Solution { public int numIslands(char[][] grid) { int cnt0; //如果发现岛屿则淹没岛屿 for(int i0;igrid.length;i){ for(int j0;jgrid[0].length;j){ if(grid[i][j]1){ //岛屿数1 cnt; dfs(grid, i, j); } } } return cnt; } //淹没岛屿即把相邻的1都变为0 public void dfs(char[][] grid, int i, int j){ if(igrid.length||jgrid[0].length||i0||j0) return; if(grid[i][j]0) return; if(grid[i][j]1) grid[i][j]0; dfs(grid, i1, j); dfs(grid, i-1, j); dfs(grid, i, j1); dfs(grid, i, j-1); } }第四十二题 腐烂的橘子把所有初始腐烂的橘子作为BFS的起点每一分钟腐烂向四周的新鲜橘子传播记录传播的层数分钟数最后检查是否还有新鲜橘子剩余class Solution { public int orangesRotting(int[][] grid) { //腐烂是否传播标志位 int rot0; if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int cnt0; Dequeint[] queuenew ArrayDeque(); //找出所有烂橘子 for(int i0;igrid.length;i){ for(int j0;jgrid[0].length;j){ if(grid[i][j]2){ queue.offer(new int[]{i, j}); } } } while(!queue.isEmpty()){ Dequeint[] queueNewnull; if(!queue.isEmpty()){ //腐烂传播 queueNewbfs(grid, queue); } //计时器 cnt; //腐烂在传播 rot1; //新的腐烂队列 queuequeueNew; } //检查是否还有新鲜橘子 for(int i0;igrid.length;i){ for(int j0;jgrid[0].length;j){ if(grid[i][j]1){ return -1; } } } //检查是否腐烂传播 if(rot1){ return cnt-1; }else{ return 0; } } public Dequeint[] bfs(int[][] grid, Dequeint[] queue){ Dequeint[] queueNewnew ArrayDeque(); while(!queue.isEmpty()){ int[] orangequeue.poll(); int iorange[0]; int jorange[1]; if(i1grid.length){ if(grid[i1][j]1){ grid[i1][j]2; queueNew.offer(new int[]{i1, j}); } } if(i-10){ if(grid[i-1][j]1){ grid[i-1][j]2; queueNew.offer(new int[]{i-1, j}); } } if(j1grid[0].length){ if(grid[i][j1]1){ grid[i][j1]2; queueNew.offer(new int[]{i, j1}); } } if(j-10){ if(grid[i][j-1]1){ grid[i][j-1]2; queueNew.offer(new int[]{i, j-1}); } } } return queueNew; } }第四十三题 课程表将课程依赖关系构建成有向图统计每个课程的入度前置课程数量从入度为0的课程开始学习BFS/队列每学完一门课它的后续课程入度减1同时计数器表明又修了一门课如果出现新的入度为0的课程加入队列最后检查是否学完了所有课程class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //创建图表示课之间的依赖关系 ListListInteger graphnew ArrayList(); //创建入度统计数组 int[] indegreenew int[numCourses]; //初始化两个数据结构 for(int i0;inumCourses;i){ graph.add(new ArrayList()); } for(int i0;iprerequisites.length;i){ //子课 int courseprerequisites[i][0]; //父课 int prerequisiteprerequisites[i][1]; graph.get(prerequisite).add(course); //课程的依赖数目 indegree[course]; } //创建队列和计数器并初始化 DequeInteger queuenew ArrayDeque(); int cnt0; for(int i0;iindegree.length;i){ if(indegree[i]0){ queue.offer(i); } } //出队列找子课减入度判断是否可修 while(!queue.isEmpty()){ //修完这门课计数器 int coursequeue.poll(); cnt; //找到所有依赖这门课的子课他们的依赖数目-- ListInteger listgraph.get(course); for(int i0;ilist.size();i){ indegree[list.get(i)]--; //子课入度为0表明可修 if(indegree[list.get(i)]0){ queue.offer(list.get(i)); } } } //判断实际修的课程数是否对应 if(cntnumCourses) return true; return false; } }第四十四题 实现trie利用哈希表作为叶子节点存储具体思路见代码注释class Trie { private class TrieNode{ //结束标志位 boolean end; //TrieNode的子节点存在哈希结构中 MapCharacter, TrieNode map; public TrieNode(boolean end, MapCharacter, TrieNode map){ this.endend; this.mapmap; } } //root是一个不存储任何字符的起始点从第二层开始才存储字符 private TrieNode root; public Trie(){ root new TrieNode(false, new HashMap()); } //插入 public void insert(String word) { TrieNode curroot; //修改结束标志位 cur.endfalse; char[] arrword.toCharArray(); //插入每个元素 for(int i0;iarr.length;i){ //如果哈希表不包括这个字符则新添加进哈希 if(!cur.map.containsKey(arr[i])){ TrieNode nodenew TrieNode(false, new HashMap()); cur.map.put(arr[i], node); } //切换到末尾继续添加或结束 curcur.map.get(arr[i]); //添加完最后一个元素修改结束标志位 if(iarr.length-1) cur.endtrue; } } //查询 public boolean search(String word) { char[] arrword.toCharArray(); TrieNode curroot; for(int i0;iarr.length;i){ //查询哈希表如果不包括这个元素直接返回false如果包含继续迭代查询 if(!cur.map.containsKey(arr[i])){ return false; }else{ curcur.map.get(arr[i]); } } //最后返回标志位因为如果标志位为false表明当前没结束表明trie中没有存储这个单词只是存储了和单词重合的前缀 return cur.end; } //前缀查询 public boolean startsWith(String prefix) { char[] arrprefix.toCharArray(); TrieNode curroot; for(int i0;iarr.length;i){ TrieNode nodecur.map.get(arr[i]); if(nodenull) return false; //如果当前长度和前缀长度相等表明前缀查询到直接返回true。这里不用考察结束标志位因为本身就是前缀不需要结束 if(iarr.length-1) return true; curcur.map.get(arr[i]); } return false; } } /** * Your Trie object will be instantiated and called as such: * Trie obj new Trie(); * obj.insert(word); * boolean param_2 obj.search(word); * boolean param_3 obj.startsWith(prefix); */第四十五题 全排列通过递归在每一层尝试所有未被选择的数字用selected数组标记已用元素当路径长度等于数组长度时收集结果然后撤销选择继续尝试其他分支直到穷举所有可能的排列顺序。class Solution { public ListListInteger permute(int[] nums) { //判断相同索引的num是否被选择 boolean[] selected new boolean[nums.length]; ListListInteger resnew ArrayList(); backTrack(nums, res, new ArrayList(), selected); return res; } public void backTrack(int[] nums, ListListInteger res, ListInteger list, boolean[] selected){ //如果当前的线路包含了所有nums的元素表明这是一条完整的链将这条线路放入res中返回 if(list.size()nums.length){ res.add(new ArrayList(list)); return; } //对于nums中的每个元素进行遍历 for(int i0;inums.length;i){ //如果当前元素被选择表明在前序层被选择跳过选其他元素 if(selected[i]) continue; //当前元素没被选择立刻选择当前元素修改selected为true表明被选择 selected[i]true; //把当前元素加入到线路中 list.add(nums[i]); //递归调用本方法 backTrack(nums, res, list, selected); //返回上一层时需要注意把当前选择的元素i拿出list队列这样才能在上一层选择i也要把selected相应位置置为false list.remove(list.size()-1); selected[i]false; } return; } }第四十六题 子集思路和上一题差不多重要的是记得每次添加都返回而且添加完成后循环从当前位置开始不从0开始class Solution { public ListListInteger subsets(int[] nums) { ListListInteger resnew ArrayList(); boolean[] selectednew boolean[nums.length]; int cnt0; backTrace(cnt, nums, selected, new ArrayList(), res); res.add(new ArrayList()); return res; } public void backTrace(int cnt, int[] nums, boolean[] selected, ListInteger list, ListListInteger res){ //cnt的作用就是让循环从当前位置开始 for(int icnt;inums.length;i){ if(selected[i]) continue; list.add(nums[i]); //每次新加都要把list添加进res res.add(new ArrayList(list)); selected[i]true; backTrace(cnt, nums, selected, list, res); list.remove(list.size()-1); selected[i]false; } return; } }第四十七题 电话号码的字母组合首先通过数组把数字和字符进行映射初始化变量res是最终返回值index是一次拼接的字母个数同时也是已经拼接的位数。path是一次拼接的具体内容回溯函数具体实现见注释class Solution { private String[] mapping{, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; public ListString letterCombinations(String digits) { ListString resnew ArrayList(); //path是一条完整的拼接链 StringBuilder pathnew StringBuilder(); //index的含义是返回值String[]中的一个元素的长度也对应着digits的长度 int index0; traceBack(digits, index, res, path); return res; } public void traceBack(String digits, int index, ListString res, StringBuilder path){ //如果当前拼接长度达到了digits的长度表明digits中所有字符的映射都被选择过一次表明这已经是一条完整的链。将path添加进String[] if(indexdigits.length()){ res.add(path.toString()); return; } //得到index位的字符及其映射字符串。比如digits是23index是1那么得到的digit就是3letters就是def char digitdigits.charAt(index); String lettersmapping[digit-0]; //取出letters中的所有元素挨个递归调用 for(int i0;iletters.length();i){ //构建path把第i个字符添加进path path.append(letters.charAt(i)); traceBack(digits, index1, res, path); //这里注意是index1因为这样不改变当前层的index值。如果是index或者index都会改变当前层的index值 //回溯删去末尾的元素 path.deleteCharAt(path.length()-1); } } }第四十八题 组合总和将数组排序在递归中从index开始遍历元素对于当前元素如果加上后等于目标值则记录结果并回溯大于目标值则直接剪枝跳出循环小于目标值则加入路径并继续递归允许重复使用当前元素递归返回后撤销选择尝试下一个元素最终找出所有和为 target 的不重复组合。class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger resnew ArrayList(); Arrays.sort(candidates); traceBack(candidates, target, new ArrayList(), 0, 0, res); return res; } public void traceBack(int[] candidates, int target, ListInteger path, int sum, int index, ListListInteger res){ for(int iindex;icandidates.length;i){ int numcandidates[i]; //如果sumnumtarget找到一条路径加入 if(sumnumtarget){ //加入列表 path.add(num); res.add(new ArrayList(path)); //不递归直接回溯 path.remove(path.size()-1); } //sumnumtarget直接爆掉 if(sumnumtarget){ break; } //sumnumtarget继续回溯 if(sumnumtarget){ //加入列表 path.add(num); //递归回溯 traceBack(candidates, target, path, sumnum, i, res); path.remove(path.size()-1); } } return; } }第四十九题 括号生成回溯通过控制左右括号数量保证合法性class Solution { // SetString setnew HashSet(); public ListString generateParenthesis(int n) { ListString listnew ArrayList(); StringBuilder sbnew StringBuilder(); sb.append((); backTrack(n, list, sb, 1, 0); return list; } public void backTrack(int n, ListString list, StringBuilder sb, int left, int right){ if(sb.length()2*n){ list.add(sb.toString()); // set.add(sb.toString()); return; } if(leftn){ sb.append((); backTrack(n, list, sb, left1, right); sb.delete(sb.length()-1, sb.length()); } if(rightleft){ sb.append()); backTrack(n, list, sb, left, right1); sb.delete(sb.length()-1, sb.length()); } } }第五十题 单词搜索见代码注释具体思路可以参考图部分的题目结合回溯class Solution { public boolean exist(char[][] board, String word) { //位图控制当前元素是否访问 boolean[][] bitmapnew boolean[board.length][board[0].length]; //词长和已访问长度控制访问次数 int numword.length(); int index0; //遍历所有元素找出所有起点 for(int i0;iboard.length;i){ for(int j0;jboard[0].length; j){ if(board[i][j]word.charAt(index)){ //调用函数开始递归 if(search(board, word, num, index, i, j, bitmap)){ return true; }else{ continue; } } } } return false; } public boolean search(char[][] board, String word, int num, int index, int i, int j, boolean[][] bitmap){ //如果走完长度并且最后一个元素匹配表明这是一条完整路径直接返回true因为代码构造问题这里的判断条件是两个 if(index1numboard[i][j]word.charAt(index)) return true; //修改访问位图把当前元素改为已访问 bitmap[i][j]true; //设置四个方向的返回值 boolean res1false, res2false, res3false, res4false; //如果当前元素匹配并且不为最后一个进入条件并递归调用 if(board[i][j]word.charAt(index)){ //判断是否越界且单元格内元素不能重复使用 if(i1board.lengthbitmap[i1][j]false){ res1search(board, word, num, index1, i1, j, bitmap); } if(i-10bitmap[i-1][j]false){ res2search(board, word, num, index1, i-1, j, bitmap); } if(j1board[0].lengthbitmap[i][j1]false){ res4search(board, word, num, index1, i, j1, bitmap); } if(j-10bitmap[i][j-1]false){ res3search(board, word, num, index1, i, j-1, bitmap); } } //回溯 bitmap[i][j]false; //只要有一个方向走通就表明找到了一条路径即返回true return res1||res2||res3||res4; } }从字符串起始位置index开始逐个尝试所有可能的起始位置i取出子串s[index:i1]进行回文检查如果是回文则加入路径然后递归处理剩余部分起始位置为i1如果不是回文则直接跳过。当index达到字符串末尾时将当前路径加入结果集通过回溯撤销选择继续尝试其他分割方式最终找出所有将原串分割成回文子串的方案class Solution { public ListListString partition(String s) { ListListString resnew ArrayList(); //index指的是将来被分割的字串的起始字符 int index0; generate(s, res, new ArrayList(), index); return res; } public void generate(String s, ListListString res, ListString path, int index){ //如果待分割的串的起始字符已经超过了父串的长度那么表明已经分割完毕且已经找到一条path添加并返回 if(indexs.length()){ res.add(new ArrayList(path)); return; } //已经确定了分割的起始点即index现在尝试每个字符作为中止点尝试是否index~end是一个回文 for(int iindex;is.length();i){ //摘出待检测待分割的子串 String subStrings.substring(index, i1); //如果是则继续递归调用该方法继续分割接下来还未被分割的串 if(check(subString)){ path.add(subString); //递归调用i1代表下一子串起始点后移一位 generate(s, res, path, i1); //回溯 path.remove(path.size()-1); } //如果不是for循环i查看index~end1是否为回文子串 } } //用左右指针检查回文 public boolean check(String s){ char[] arrs.toCharArray(); int left0, rightarr.length-1; while(leftright){ if(s.charAt(left)!s.charAt(right)) return false; left; right--; } return true; } }