leetcode338-leetcode-java:力扣Java解决方案

# leetcode-java LeetCode Java Solution ## 题目 ### [递归](#recursion) - [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)：[【104题解】](#104题解) - [226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)：[【226题解】](#226题解) - [112. 路径总和](https://leetcode-cn.com/problems/path-sum/)：[【112题解】](#112题解) - [257. 二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/)：[【257题解】](#257题解) - more - [111. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/) - [100. 相同的树](https://leetcode-cn.com/problems/same-tree/) - [101. 对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/) - [222. 完全二叉树的节点个数](https://leetcode-cn.com/problems/count-complete-tree-nodes/) - [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) - [404. 左叶子之和](https://leetcode-cn.com/problems/sum-of-left-leaves/) - [113. 路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/) - [129. 求根节点到叶节点数字之和](https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/) ### [回溯](#backtracking) - [17. 电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)：[【17题解】](#17题解) - [46. 全排列](https://leetcode-cn.com/problems/permutations/)：[【46题解】](#46题解) - [77. 组合](https://leetcode-cn.com/problems/combinations/)：[【77题解】](#77题解) - [79. 单词搜索](https://leetcode-cn.com/problems/word-search/)：[【79题解】](#79题解) - [200. 岛屿数量](https://leetcode-cn.com/problems/number-of-islands/)：[【200题解】](#200题解) - [51. N 皇后](https://leetcode-cn.com/problems/n-queens/)：[【51题解】](#51题解) more - [93. 复原 IP 地址](https://leetcode-cn.com/problems/restore-ip-addresses/) - [131. 分割回文串](https://leetcode-cn.com/problems/palindrome-partitioning/) - [47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/) - [39. 组合总和](https://leetcode-cn.com/problems/combination-sum/) - [40. 组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/) - [216. 组合总和 III](https://leetcode-cn.com/problems/combination-sum-iii/) - [78. 子集](https://leetcode-cn.com/problems/subsets/)：[【78题解】](#78题解) - [90. 子集 II](https://leetcode-cn.com/problems/subsets-ii/) - [401. 二进制手表](https://leetcode-cn.com/problems/binary-watch/) - [130. 被围绕的区域](https://leetcode-cn.com/problems/surrounded-regions/) - [417. 太平洋大西洋水流问题](https://leetcode-cn.com/problems/pacific-atlantic-water-flow/) - [37. 解数独](https://leetcode-cn.com/problems/sudoku-solver/) ### [位运算](#bitoperation) - [461. 汉明距离](https://leetcode-cn.com/problems/hamming-distance/)：[【461题解】](#461题解) - [338. 比特位计数](https://leetcode-cn.com/problems/counting-bits/)：[【338题解】](#338题解) ## 题解 ### recursion ### 104题解 - 解法：递归 - 复杂度：O(n)、O(h) ```java class Solution { public int maxDepth(TreeNode root) { // 递归终止条件 if(root == null) { return 0; } // 递归过程 return Math.max(maxDepth(root.left), maxDepth(root.right))+1; } } ``` ### 226题解 - 解法：递归 - 复杂度：O(n)、O(h) ```java class Solution { public TreeNode invertTree(TreeNode root) { // 递归终止条件 if(root == null) { return null; } // 递归过程 // 错误写法：root.left=invertTree(root.right); TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); // swap root.left = right; root.right = left; return root; } } ``` ### 112题解 - 解法：递归 - 复杂度：O(n)、O(h) ```java class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { // 边界条件 if(root == null) { return false; } // 叶子节点：左右子树均为null if(root.left==null && root.right==null) { return root.val == targetSum; } // 找左子树 if(hasPathSum(root.left, targetSum-root.val)) { return true; } // 找右子树 if(hasPathSum(root.right, targetSum-root.val)) { return true; } // 没找到 return false; } } ``` ### 257题解 - 解法：递归 - 复杂度：O(n)、O(h) ```java class Solution { List<String> res = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { helper(root, ""); return res; } private void helper(TreeNode root, String path) { // 递归终止条件 if(root == null) { return; } if(root.left==null && root.right==null) { path += root.val; res.add(path); } // 递归过程 path += root.val + "->"; helper(root.left, path); helper(root.right, path); } } ``` ### backtracking #### 17题解 - 解法：回溯 - 复杂度：O(2 x len(s))、O(len(s)) ```java class Solution { final String[] letterMap = { " ", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz", // 9 }; private List<String> res = new ArrayList<>(); public List<String> letterCombinations(String digits) { // 边界情况：空串 if(digits.equals("")) { return res; } backtrack(digits, 0, ""); return res; } /** * 回溯辅助函数，得到每一个字母的树排列 * @param digits 数字字符串 * @param index 第几个数字 * @param s 前index个的字母字符串 */ private void backtrack(String digits, int index, String s) { // 递归终止条件：index与digits长度相等 if(index == digits.length()) { // 保存s res.add(s); return; } char c = digits.charAt(index); // 边界情况：字符串合法性 assert( c>='0' && c<='9' && c!='1'); String letters = letterMap[c-'0']; // 遍历字母字符串 for(int i=0; i<letters.length(); i++) { // s <== s+letters.charAt(i) backtrack(digits, index+1, s+letters.charAt(i)); } } } ``` ### 46题解 - 解法：回溯 - 复杂度：O(n^n)、O(n) ```java class Solution { private List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { backtrak(nums, 0, new ArrayList<>()); return res; } /** * 回溯辅助函数 * @param nums 数组 * @param index 当前下标 * @param path 路径的值 */ private void backtrak(int[] nums, int index, List<Integer> path) { // 递归终止条件：index与nums长度相等 if(index == nums.length) { res.add(new ArrayList<>(path)); return; } for(int i=0; i<nums.length; i++) { // 判断nums[i]是否在path中 if(!path.contains(nums[i])) { path.add(nums[i]); // 递归操作 backtrak(nums, index+1, path); // 回溯操作 path.remove(path.size()-1); } } } } ``` ### 77题解 - 解法：回溯 - 复杂度：O(n^k)、O(k) ```java class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { // 边界判断 if(n<=0 || k<