1. 题目
https://leetcode-cn.com/problems/climbing-stairs/https://leetcode-cn.com/problems/generate-parentheses/https://leetcode-cn.com/problems/invert-binary-tree/description/https://leetcode-cn.com/problems/validate-binary-search-treehttps://leetcode-cn.com/problems/maximum-depth-of-binary-treehttps://leetcode-cn.com/problems/minimum-depth-of-binary-treehttps://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversalhttps://leetcode-cn.com/problems/combinations/https://leetcode-cn.com/problems/permutations/https://leetcode-cn.com/problems/permutations-ii/
2. 题解
2.1 爬楼梯#70（简单）
class Solution {
public int climbStairs(int n) {
//❌超时
//法一:递归,时间复杂度O(2^n),空间复杂度O(2^n)
if (n <= 2) {
return n;
}
return climbStairs(n-1) + climbStairs(n-2);
}
}
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
//法二:递归+记忆化,时间复杂度O(n),空间复杂度O(n)
if (n < 3) {
return n;
}
if (map.containsKey(n)) {
return map.get(n);
}
int sum = climbStairs(n-1) + climbStairs(n-2);
map.put(n, sum);
return sum;
}
}
class Solution {
public int climbStairs(int n) {
//法三:迭代,时间复杂度O(n),空间复杂度O(1)
if (n < 3) {
return n;
}
int a = 1, b = 2, c = 0;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
//这里return b或者return c都是可以的
return b;
}
}
class Solution {
public int climbStairs(int n) {
//法四:动态规划,时间复杂度O(n),空间复杂度O(1)
int a = 0, b = 0, c = 1;
for (int i = 1; i <= n; i++) {
//这里要从1开始，保证只循环n次
a = b;
b = c;
c = a + b;
}
//这里就只能return c
return c;
}
}
2.2 括号生成#22（中等）
class Solution {
public List<String> generateParenthesis(int n) {
//法一:递归.时间复杂度O(n * 2^2n),空间复杂度O(n)
//判断每一种情况是否有效要时间复杂度O(n)
//一共生成2^2n种情况，所以是二者相乘的时间复杂度
//一共递归2n层，每层需要空间O(1)
List<String> ans = new LinkedList<>();
//n对括号,会有2n个位置放置括号
char[] possible = new char[2*n];
generateAll(possible, 0, ans);
return ans;
}
private void generateAll(char[] current, int pos, List<String> ans) {
if (pos == current.length) {
if (valid(current)) {
ans.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, ans);
current[pos] = ')';
generateAll(current, pos + 1, ans);
}
}
private boolean valid(char[] current) {
int num = 0;
for (char c : current) {
if (c == '(') {
num++;
} else if (c == ')') {
num--;
}
if (num < 0) {
return false;
}
}
return num == 0;
}
}
class Solution {
public List<String> generateParenthesis(int n) {
//法二:回溯.时间复杂度和空间复杂度见官方题解
//在法一的基础上，只需要在当前括号是有效的情况下再进行添加括号
List<String> ans = new LinkedList<>();
backtrace(ans, new StringBuilder(), 0, 0, n);
return ans;
}
private void backtrace(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == 2*max) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append("(");
backtrace(ans, cur, open+1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(")");
backtrace(ans, cur, open, close+1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}
class Solution {
ArrayList[] cache = new ArrayList[100];
public List<String> generateParenthesis(int n) {
//法三:按括号序列的长度递归。时间复杂度和空间复杂度见官方题解。
//这个方法有点难以理解，要把官方题解再多看几遍。
return generate(n);
}
private List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left : generate(c)) {
for (String right : generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
}
2.3 翻转二叉树#226（简单）
https://leetcode-cn.com/problems/invert-binary-tree/description/
class Solution {
public TreeNode invertTree(TreeNode root) {
//方法一：深度后序递归,时间复杂度O(n),空间复杂度O(n)
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
2.4 验证二叉搜索树#98（中等）
https://leetcode-cn.com/problems/validate-binary-search-tree
class Solution {
public boolean isValidBST(TreeNode root) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode node, long low, long high) {
if (node == null) {
return true;
}
if (node.val <= low || node.val >= high) {
return false;
}
return helper(node.left, low, node.val) && helper(node.right, node.val, high);
}
}
class Solution {
public boolean isValidBST(TreeNode root) {
//法二:中序遍历(官方题解).时间复杂度O(n),空间复杂度O(n)
Deque<TreeNode> stack = new LinkedList<>();
double inorder = -Double.MAX_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
}
}
class Solution {
public boolean isValidBST(TreeNode root) {
//法三:中序遍历.时间复杂度O(n),空间复杂度O(n)
List<Long> list = new LinkedList<>();
inOrder(root, list);
long pre = Long.MIN_VALUE;
for (long e : list) {
if (e <= pre) {
return false;
}
pre = e;
}
return true;
}
private void inOrder(TreeNode node, List<Long> list) {
if (node == null) {
return;
}
inOrder(node.left, list);
list.add((long) node.val);
inOrder(node.right, list);
}
}
class Solution {
Long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//法四:中序遍历优化写法.时间复杂度O(n),空间复杂度O(n)
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (root.val <= pre) {
return false;
}
pre = (long) root.val;
return isValidBST(root.right);
}
}
2.5 二叉树的最大深度#104（简单）
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
class Solution {
public int maxDepth(TreeNode root) {
//法一:深度优先搜索.时间复杂度O(n),空间复杂度O(height)
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
class Solution {
public int maxDepth(TreeNode root) {
//法二:广度优先搜索.时间复杂度O(n),空间复杂度O(n)
if (root == null) {
return 0;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}
2.6 二叉树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
class Solution {
public int minDepth(TreeNode root) {
//法一:递归+深度优先搜索.时间复杂度O(n),空间复杂度O(n)
if (root == null) {
return 0;
}
int leftHeight = minDepth(root.left);
int rightHeight = minDepth(root.right);
return (leftHeight == 0 || rightHeight == 0) ? leftHeight + rightHeight + 1 : Math.min(leftHeight, rightHeight) + 1;
}
}
class Solution {
public int minDepth(TreeNode root) {
//法二:广度优先搜索.时间复杂度O(n),空间复杂度O(n)
if (root == null) {
return 0;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return level;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
level++;
}
return level;
}
}
2.7 二叉树的序列化与反序列化#297（困难）
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
//DFS前序遍历
return rserialize(root, "");
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] array = data.split(",");
List<String> dataList = new LinkedList<String>(Arrays.asList(array));
return rdeserialize(dataList);
}
private String rserialize(TreeNode node, String str) {
if (node == null) {
str += "None,";
} else {
str += str.valueOf(node.val) + ",";
str = rserialize(node.left, str);
str = rserialize(node.right, str);
}
return str;
}
private TreeNode rdeserialize(List<String> dataList) {
if (dataList.get(0).equals("None")) {
dataList.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
root.left = rdeserialize(dataList);
root.right = rdeserialize(dataList);
return root;
}
}
2.8 二叉树的最近公共祖先#236（中等）
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//法一展开写法:DFS+递归,时间复杂度O(n),空间复杂度O(n)
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;
}
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//法一优化:DFS+递归,时间复杂度O(n),空间复杂度O(n)
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) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}
2.9 从前序与中序遍历序列构造二叉树#105（中等）
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution {
//用来存放中序遍历的节点值和下标的对应关系
private Map<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
int n = preorder.length;
//构造哈希表，找到根节点的下标
indexMap = new HashMap<>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
//如果长度小于0
return null;
}
//前序遍历的第一个节点就是根节点
int preorder_root = preorder_left;
//根节点在中序遍历中的下标
int inorder_root = indexMap.get(preorder[preorder_root]);
//建立根节点
TreeNode root = new TreeNode(preorder[preorder_root]);
//找到左子树中的节点数量
int left_subtree_size = inorder_root - inorder_left;
//递归构造左子树，并连接到根节点
//先序遍历中 从左边界+1开始的left_subtree_size 个元素
//对应中序遍历中从 左边界开始到根节点定位-1的元素
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_subtree_size, inorder_left, inorder_root - 1);
//递归构造又子树，同上
root.right = myBuildTree(preorder, inorder, preorder_left + left_subtree_size + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
}
2.10 组合#77（中等）
class Solution {
public List<List<Integer>> combine(int n, int k) {
//法一:根据搜索起点画出二叉树.时间复杂度O(n),空间复杂度O(k)
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
// 从1开始是题目的设定
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
//递归终止条件是：path的长度等于k
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 遍历可能的搜索起点
for (int i = begin; i <= n; i++) {
//向路径变量添加一个数
path.addLast(i);
//下一轮搜索，设置的搜索起点要加1,因为组合数里不允许出现重复的元素
dfs(n, k, i + 1, path, res);
//重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，
//递归之后需要做相同操作的逆向操作
path.removeLast();
}
}
}
class Solution {
public List<List<Integer>> combine(int n, int k) {
//法一优化:剪枝.时间复杂度O(n),空间复杂度O(k)
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 只有i的条件不同了
for (int i = begin; i <= n - (k - path.size()) + 1; i++) {
path.addLast(i);
dfs(n, k, i + 1, path, res);
path.removeLast();
}
}
}
class Solution {
public List<List<Integer>> combine(int n, int k) {
//法二:按照每个数选与不选构造二叉树.时间复杂度O(n),空间复杂度O(k)
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
if (k == 0) {
res.add(new ArrayList<>(path));
return;
}
//基础版的递归终止条件：if (begin == n+1)
if (begin > n - k + 1) {
return;
}
//不选当前考虑的数begin,递归到下一层
dfs(n, k, begin+1, path, res);
// 不选当前考虑的数begin,递归到下一层的时候k-1，这里k表示还需要选多少个数
path.addLast(begin);
dfs(n, k-1, begin + 1, path, res);
//深度优先遍历有回头的过程，因此需要撤销选择
path.removeLast();
}
}
2.11 全排列#46（中等）
class Solution {
public List<List<Integer>> permute(int[] nums) {
//法一:回溯.时间复杂度O(n*n!),空间复杂度O(n*n!).
//复杂度的具体分析可能要看题解，我数学推导不太强
int length = nums.length;
List<List<Integer>> ans = new LinkedList<>();
if (length == 0) {
return ans;
}
//这个boolean数组是自己写的时候没有想到的，
//看了题解才意识到总觉得差一点的差的究竟是什么
boolean[] used = new boolean[length];
Deque<Integer> temp = new ArrayDeque<>();
dfs(length, nums, 0, used, ans, temp);
return ans;
}
private void dfs(int length, int[] nums, int index, boolean[] used, List<List<Integer>> ans, Deque<Integer> temp) {
if (length == index) {
ans.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < length; i++) {
if (!used[i]) {
temp.addLast(nums[i]);
//从浅到深
used[i] = true;
dfs(length, nums, index + 1, used, ans, temp);
//从深到浅，这里开始回溯
used[i] = false;
temp.removeLast();
}
}
}
}
2.12 全排列2#47（中等）
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
//法一:回溯.时间复杂度O(n*n!),空间复杂度O(n*n!)
int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();
if (length == 0) {
return ans;
}
//要去重的话，那肯定要先排个序了
Arrays.sort(nums);
boolean[] used = new boolean[length];
Deque<Integer> temp = new ArrayDeque<>();
dfs(nums, length, 0, used, temp, ans);
return ans;
}
private void dfs(int[] nums, int length, int index, boolean[] used, Deque<Integer> temp, List<List<Integer>> ans) {
if (index == length) {
ans.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < length; i++) {
if (used[i]) {
continue;
}
//剪枝条件:i>0是为了保证nums[i-1]有意义
//写!used[i-1]是因为nums[i-1]在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
temp.addLast(nums[i]);
used[i] = true;
dfs(nums, length, index + 1, used, temp, ans);
//从深回到浅,回溯开始
used[i] = false;
temp.removeLast();
}
}
}
若有收获，就点个赞吧
0 人点赞
