- 70. 爬楼梯">70. 爬楼梯
- 22. 括号生成">22. 括号生成
- 226. 翻转二叉树">226. 翻转二叉树
- 98. 验证二叉搜索树">98. 验证二叉搜索树
- 104. 二叉树的最大深度">104. 二叉树的最大深度
- 111. 二叉树的最小深度">111. 二叉树的最小深度
- 297. 二叉树的序列化与反序列化">297. 二叉树的序列化与反序列化
- 50. Pow(x, n)">50. Pow(x, n)
- 78. 子集">78. 子集
- 169. 多数元素">169. 多数元素
- 17. 电话号码的字母组合">17. 电话号码的字母组合
- 51. N 皇后">51. N 皇后
- 236. 二叉树的最近公共祖先">236. 二叉树的最近公共祖先
- 105. 从前序与中序遍历序列构造二叉树">105. 从前序与中序遍历序列构造二叉树
- 77. 组合">77. 组合
- 46. 全排列">46. 全排列
- 47. 全排列 II">47. 全排列 II
70. 爬楼梯
难度简单1459
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
class Solution {static public int climbStairs(int n) {if(n <= 2){return n;}int dp[] = new int[n+1];dp[1] = 1;dp[2] = 2;for(int i = 3;i <= n;i++){dp[i]=dp[i-1] + dp[i-2];}return dp[n];}}
递归解决：
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
return cs(1,2,2,n);
}
public int cs(int level1,int level2,int nextlevel,int n){
if(n == nextlevel){
return level2;
}
int number = level1 + level2;
return cs(level2,number,nextlevel + 1,n);
}
}
22. 括号生成
难度中等1553
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
class Solution {
/**
* 括号生成
* @param n
* @return
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
_generate(0,0,"",n,result);
return result;
}
private void _generate(int left, int right, String s, int n, List<String> result) {
//终结者
if(left == n && right == n){
//收割当前的数据
result.add(s);
return;
}
//逻辑
//进入到下一层
if(left < n){
String s1 = s + "(";
_generate(left+1,right,s1 ,n,result);
}
if(right < left){
String s2 = s + ")";
_generate(left,right+1,s2,n,result);
}
//清理当前层
}
}
226. 翻转二叉树
难度简单751
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if( null == root){
return root;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree( root.right);
root.left = right;
root.right = left;
return root;
}
}
98. 验证二叉搜索树
难度中等916
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
/**
* 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 isValidBST(TreeNode root) {
return isValid(root,null,null);
}
//上界，下届
private boolean isValid(TreeNode node,Integer lower,Integer upper){
if(node == null) return true;
int val = node.val;
if((lower != null && val <= lower) || ( upper != null && val >= upper ) ) return false;
//进入到下一层
return isValid( node.left , lower , val ) && isValid( node.right ,val , upper);
}
}
104. 二叉树的最大深度
难度简单787
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/**
* 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) {
if( null == root) return 0;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return Math.max(leftMax, rightMax)+1;
}
}
111. 二叉树的最小深度
难度简单447
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
- 树中节点数的范围在
[0, 10]内 -1000 <= Node.val <= 1000
/**
* 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 minDepth(TreeNode root) {
if( null == root){
return 0;
}
//1：左孩子和右孩子都为空的情况，说明到达了叶子结点，直接返回1
if( null == root.left && null == root.right){
return 1;
}
//2：如果左孩子和右孩子其中一个为空
int leftDepth = minDepth(root.left);
int rithtDepth = minDepth(root.right);
//
if(root.left == null || root.right == null){
return leftDepth + rithtDepth + 1;
}
return Math.min(leftDepth,rithtDepth)+1;
}
}
297. 二叉树的序列化与反序列化
难度困难466
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
提示：
- 树中结点数在范围
[0, 10]内 -1000 <= Node.val <= 1000
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root==null) return "";
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while( !queue.isEmpty()){
TreeNode pollNode = queue.poll();
if(pollNode != null){
sb.append(pollNode.val + ",");
queue.offer(pollNode.left);
queue.offer(pollNode.right);
}else{
sb.append("null,");
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if( "".equals(data.trim())){
return null;
}
String[] nodes = data.substring(0, data.length() - 1).split(",");
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//创建头结点
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
int dep = 1;
queue.offer(root);
while( !queue.isEmpty() ){
TreeNode pollNode = queue.poll();
//如果数组不为null
if( !"null".equals(nodes[dep])){
pollNode.left = new TreeNode(Integer.parseInt(nodes[dep]));
queue.offer(pollNode.left);
}
dep++;
if(!"null".equals(nodes[dep])){
pollNode.right = new TreeNode(Integer.parseInt(nodes[dep]));
queue.offer(pollNode.right);
}
dep++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
50. Pow(x, n)
难度中等576
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2 = 1/2 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-2 <= n <= 2-1-10 <= x <= 10
class Solution {
public double myPow(double x, int n) {
if(n<0){
x=1/x;
n=-n;
}
return _pow(x,n);
}
private double _pow(double x, int n) {
//终结者
if(n==0){
return 1.0;
}
//逻辑
double val = _pow(x,n/2);
return n % 2 == 0 ? val * val : val * val * x;
}
}
78. 子集
难度中等986
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if(nums == null ) return results;
//处理
_sub(results,new ArrayList<Integer>(),nums,0,nums.length);
return results;
}
private void _sub(List<List<Integer>> results, ArrayList<Integer> reslut, int[] nums, int level, int maxLevel) {
//终结者
if( level == maxLevel){
results.add(new ArrayList<Integer>(reslut));
return;
}
//逻辑
_sub(results,reslut,nums,level+1,maxLevel);
reslut.add(nums[level]);
_sub(results,reslut,nums,level+1,maxLevel);
reslut.remove(reslut.size() - 1);
}
}
169. 多数元素
难度简单866
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
- 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
class Solution {
public int majorityElement(int[] nums) {
if(nums.length==1){
return nums[0];
}
int selectSize = nums.length / 2;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
if(map.get(num) != null && map.get(num)+1 > selectSize) {
return num;
}
map.put(num,map.getOrDefault(num,0) +1);
}
return 0;
}
}
17. 电话号码的字母组合
难度中等1125
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,”b”,”c”]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
if(digits==null || digits.length() ==0) return result;
//存放按键和数字的映射关系
Map<Character,String> tels = new HashMap<Character,String>();
tels.put('2',"abc");
tels.put('3',"def");
tels.put('4',"ghi");
tels.put('5',"jkl");
tels.put('6',"mno");
tels.put('7',"pqrs");
tels.put('8',"tuv");
tels.put('9',"wxyz");
//构建数据
_build(digits,tels,result,0,"");
return result;
}
private void _build(String digits, Map<Character, String> map, List<String> result,int level,String s) {
//终结者
if( level == digits.length()){
result.add(s);
return ;
}
//逻辑
char digit = digits.charAt(level);
String s1 = map.get(digit);
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
_build(digits,map,result,level+1,s+c);
}
}
}
51. N 皇后
难度困难746
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[[“Q”]]
提示：
1 <= n <= 9- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
236. 二叉树的最近公共祖先
难度中等929
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5和节点 1的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5和节点 4的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围
[2, 10]内。 -10 <= Node.val <= 10- 所有
Node.val互不相同。 p != qp和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) {
if(root == null || root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if( left == null && right == null ){
return null;
}
if( left == null ){
return right;
}
if(right == null){
return left;
}
return root;
}
}
105. 从前序与中序遍历序列构造二叉树
难度中等866
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len = preorder.length;
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < len; i++) {
map.put(inorder[i],i);
}
return buildTree(preorder,0,len - 1,0,len - 1,map);
}
/**
*
* @param preorder 前序遍历序列
* @param preorder_left 前序遍历序列子区间的左边界，可以计算出来
* @param preorder_right 前序遍历序列子区间右边界，可以计算出来
* @param inorder_left 中序遍历序列子区间左边界，可以计算出来
* @param inorder_right 中序遍历序列子区间右边界，可以计算出来
* @param map 在中序遍历序列里，数值与下标对应关系
* @return
*/
private TreeNode buildTree(int[] preorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right, Map<Integer,Integer> map) {
if( preorder_left > preorder_right){
return null;
}
//前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
//在中序遍历中定位根节点，在中序的序列中找到对应的根节点的下标位置
int inorder_root = map.get(preorder[preorder_root]);
//建立根节点
TreeNode root = new TreeNode(preorder[preorder_root]);
//得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
//递归的构造左子树
root.left = buildTree(preorder,preorder_left + 1,preorder_left + size_left_subtree, inorder_left ,inorder_root - 1,map);
//递归的构造右子树
root.right = buildTree(preorder,preorder_left + size_left_subtree + 1,preorder_right,inorder_root+1,inorder_right,map);
return root;
}
}
77. 组合
难度中等486
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combine(int n, int k) {
_dfs(n,k,1);
return result;
}
private void _dfs(int n, int k,int level) {
//终止条件 temp.size() == k时，说明temp中已经存放了2个元素了，就收割数据
if(temp.size() == k){
result.add(new ArrayList<Integer>(temp));
return;
}
//树的宽度 for循环,从level --- n
for (int i = level; i <= n; i++) {
//收割此节点的数据
temp.add(i);
//树的深度 递归
_dfs(n,k,i+1);
//回溯
temp.remove(temp.size()-1);
}
}
}
46. 全排列
难度中等1119
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> permute(int[] nums) {
_dfs(nums,nums.length,0);
return result;
}
private void _dfs(int[] nums, int maxLen, int level) {
//如果temp中的数据元素有maxLen个了，说明排列完了，就收割数据
if(temp.size() == maxLen) {
result.add(new ArrayList<Integer>(temp));
return;
}
//树的宽度
for (int i = 0; i < maxLen; i++) {
if(!temp.contains(nums[i])){
//收割数据
temp.add(nums[i]);
//树的深度 递归
_dfs(nums,maxLen,i+1);
//回溯
temp.remove(temp.size() - 1);
}
}
}
}
47. 全排列 II
难度中等586
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
若有收获，就点个赞吧
0 人点赞
