面试中最常考的（分类的稍微有点粗糙了，没有细分出回溯/分治来，准备找个时间给每个DFS的题标记下是哪种DFS）
- 基础知识：
常见的DFS用来解决什么问题？
（1）图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度
（2）排列组合
（3） 遍历一个图（或者树）
（4）找出图或者树中符合题目要求的全部方案
DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值）
除了遍历之外多数情况下时间复杂度是指数级别，一般是O(方案数×找到每个方案的时间复杂度)
递归题目都可以用非递归迭代的方法写，但一般实现起来非常麻烦
- 基于树的DFS：需要记住递归写前序中序后序遍历二叉树的模板
Leetcode 543 Diameter of Binary Tree (分治)
Leetcode 124 Binary Tree Maximum Path Sum (分治)
Leetcode 226 Invert Binary Tree (分治)
Leetcode 101 Symmetric Tree (回溯 or 分治)
Leetcode 951 Flip Equivalent Binary Trees (分治)
Leetcode 236 Lowest Common Ancestor of a Binary Tree (相似题：235、1650) (回溯 or 分治)
Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal (分治)
Leetcode 104 Maximum Depth of Binary Tree (回溯 or 分治)
Leetcode 987 Vertical Order Traversal of a Binary Tree
Leetcode 1485 Clone Binary Tree With Random Pointer
Leetcode 572 Subtree of Another Tree (分治)
Leetcode 863 All Nodes Distance K in Binary Tree
Leetcode 1110 Delete Nodes And Return Forest (分治)
- 二叉搜索树（BST）：BST特征：中序遍历为单调递增的二叉树，换句话说，根节点的值比左子树任意节点值都大，比右子树任意节点值都小，增删查改均为O（h）复杂度，h为树的高度；注意不是所有的BST题目都需要递归，有的题目只需要while循环即可
Leetcode 230 Kth Smallest element in a BST
Leetcode 98 Validate Binary Search Tree
Leetcode 270 Cloest Binary Search Tree Value
Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
Leetcode 669 Trim a Binary Search Tree (分治)
Leetcode 700 Search in a Binary Search Tree
Leetcode 108 Convert Sorted Array to Binary Search Tree (分治)
Leetcode 333 Largest BST Subtree (与98类似) (分治)
Leetcode 285 Inorder Successor in BST (I, II)
- 基于图的DFS: 和BFS一样一般需要一个set来记录访问过的节点，避免重复访问造成死循环; Word XXX 系列面试中非常常见，例如word break，word ladder，word pattern，word search。
Leetcode 341 Flatten Nested List Iterator (339 364)
Leetcode 394 Decode String
Leetcode 51 N-Queens (I II基本相同)
Leetcode 291 Word Pattern II (I为简单的Hashmap题)
Leetcode 126 Word Ladder II （I为BFS题目）
Leetcode 93 Restore IP Addresses
Leetcode 22 Generate Parentheses
Leetcode 586 Score of Parentheses
Leetcode 301 Remove Invalid Parentheses
Leetcode 37 Sodoku Solver
Leetcode 212 Word Search II （I, II）
Leetcode 1087 Brace Expansion
Leetcode 399 Evaluate Division
Leetcode 1274 Number of Ships in a Rectangle
Leetcode 1376 Time Needed to Inform All Employees
Leetcode 694 Number of Distinct Islands
Leetcode 131 Palindrome Partitioning
Leetcode 543 Diameter of Binary Tree (分治)
题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
解法
本题的解法是递归。对于任意一个节点，它的直径长度可以由它的左子树的最大深度加上右子树的最大深度得到。因此，我们可以递归地求出每个节点的最大深度，同时记录下经过该节点的直径长度的最大值。
具体地，对于任意一个节点，我们定义一个递归函数 depth(node) 表示该节点的最大深度，函数计算过程如下：
-
如果当前节点为空，则返回深度 0。
-
否则，递归计算左右子节点的最大深度：left = depth(node.left)，right = depth(node.right)。
-
我们可以用这两个子节点的最大深度更新答案，即 diameter = max(diameter, left + right)。
-
返回该节点的最大深度，即max(left, right) + 1。
最后，我们可以在递归过程中维护一个全局变量 diameter，表示经过某个节点的最大直径长度。
代码
class Solution {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
private int depth(TreeNode node) {
if (node == null) {
return 0;
}
int left = depth(node.left);
int right = depth(node.right);
diameter = Math.max(diameter, left + right);
return Math.max(left, right) + 1;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。对每个节点访问不超过 2 次，每次访问操作的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
空间复杂度：O(height)，其中 height 表示二叉树的高度。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下二叉树的高度等于节点个数，空间复杂度为 O(n)。平均情况下二叉树的高度与节点个数的对数正相关，空间复杂度为 O(logn)。
Leetcode 124 Binary Tree Maximum Path Sum (分治)
题目描述
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
解法
本题可以使用递归的方法来解决。对于二叉树中的每个节点，我们可以分别计算包含该节点的最大路径和以及不包含该节点的最大路径和。最终答案即为所有节点中包含该节点的最大路径和中的最大值。
具体地，我们可以定义一个递归函数 dfs(node)，它计算以 node 为根节点的子树中包含 node 的最大路径和以及不包含 node 的最大路径和，并返回以 node 为根节点的子树中包含 node 的最大路径和。
在递归函数中，我们首先递归计算 node 的左右子树的结果，即 left = dfs(node.left) 和 right = dfs(node.right)。对于包含 node 的最大路径和，它有两种情况：
-
如果左右子树的最大路径和都为正数，那么以
node为根节点的子树中包含node的最大路径和为node.val + left + right。 -
如果左右子树的最大路径和中至少有一个为负数，那么以
node为根节点的子树中包含node的最大路径和为node.val + max(left, right)。
对于不包含 node 的最大路径和，它有三种情况：
-
如果左右子树的最大路径和都为负数，那么以
node为根节点的子树中不包含node的最大路径和为node.val。 -
如果左右子树的最大路径和中至少有一个为正数，那么以
node为根节点的子树中不包含node的最大路径和为max(left, right)。 -
如果左右子树的最大路径和都为正数，那么以
node为根节点的子树中不包含node的最大路径和为node.val + max(left, right)。
最终，我们可以将包含 node 的最大路径和和不包含 node 的最大路径和中的最大值作为以 node 为根节点的子树中的最大路径和，并返回该值。
代码
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
}
复杂度分析
时间复杂度：，其中 是二叉树中的节点个数。我们对每个节点只访问了一次。
空间复杂度：，其中 是二叉树的高度。递归函数会在递归的过程中使用到栈空间，因此空间复杂度为 。由于本题中二叉树不一定是平衡的，因此 可能会达到 ，空间复杂度最坏情况下为 。
Leetcode 226 Invert Binary Tree (分治)
题目描述
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
解法
使用递归的方式进行翻转。对于每个节点，我们先将其左右子树翻转，然后交换左右子树。
代码
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树的节点数。我们每个节点只访问一次，因此时间复杂度为 O(n)。
空间复杂度：O(h)，其中 h 是二叉树的高度。这里的空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下二叉树退化为链表，空间复杂度为 O(n)，平均情况下二叉树的高度与节点数的对数正相关，空间复杂度为 O(logn)。
Leetcode 101 Symmetric Tree (回溯 or 分治)
题目描述
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解法
方法一：递归
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
因此，该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值。
- 每个树的右子树都与另一个树的左子树镜像对称。
这是一个递归的过程，因此可以使用递归解决这个问题。
具体地，该函数从根开始，只要两个根的值相同，就递归地比较它们的子树。
- 左子树的左子树与右子树的右子树相等。
- 左子树的右子树与右子树的左子树相等。
方法二：迭代
方法一的递归过程可能会导致函数调用栈溢出。在这种情况下，可以使用迭代的方法代替递归。
可以使用队列来代替递归的方法。该队列中每个元素都包含两个节点，这些节点应该互为镜像。初始时，队列包含根的两个节点。
每次提取队列中的两个节点并比较它们的值。然后，将两个节点的左右子节点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续节点），算法结束。
代码
Java 代码
递归
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
}
}
迭代
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
continue;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
复杂度分析
时间复杂度
递归方法的时间复杂度为 ，其中 是树的节点个数。在最糟糕的情况下，树是线性的，其递归树的深度可能达到 。而迭代方法的时间复杂度也为 ，因为它需要遍历每个节点一次。
空间复杂度
递归方法的空间复杂度取决于递归树的深度，最差情况下需要达到 。迭代方法的空间复杂度是 ，因为在队列中需要存储每个节点一次。
Leetcode 951 Flip Equivalent Binary Trees (分治)
题目描述
给定两棵二叉树，判断它们是否是相同的二叉树。
如果两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
解法
本题是一个二叉树的遍历问题。对于两棵树是否相同，我们可以使用递归的方式判断。递归过程中，如果两个节点的值相同，则需要继续递归判断它们的左右子树是否相同。如果值不同，则直接返回false。如果递归到空节点，则可以直接返回true。
代码
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null || root1.val != root2.val) {
return false;
}
boolean left1 = flipEquiv(root1.left, root2.left);
boolean right1 = flipEquiv(root1.right, root2.right);
boolean left2 = flipEquiv(root1.left, root2.right);
boolean right2 = flipEquiv(root1.right, root2.left);
return (left1 && right1) || (left2 && right2);
}
}
复杂度分析
时间复杂度：，其中 是二叉树的节点数。每个节点最多会被访问两次。
空间复杂度：，其中 是二叉树的高度。递归调用的栈空间取决于二叉树的高度。
Leetcode 236 Lowest Common Ancestor of a Binary Tree (相似题：235、1650) (回溯 or 分治)
题目描述
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：对于有根树 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, 105] 内。
- -109 <= Node.val <= 109
- 所有 Node.val 互不相同 。
- p != q
- p 和 q 均存在于给定的二叉树中。
解法
题目要求我们找到两个节点的最近公共祖先，我们可以使用递归的方式来实现。
我们定义一个递归函数 lowestCommonAncestor(root, p, q)，表示在以 root 为根节点的二叉树中找到节点 p 和节点 q 的最近公共祖先。
如果当前节点 root 为 null，或者当前节点为 p 或 q 中的一个，那么我们直接返回当前节点。
否则，我们分别在左子树和右子树中查找 p 和 q，并将其结果分别保存在变量 left 和 right 中。
如果 left 和 right 均不为 null，那么当前节点即为 p 和 q 的最近公共祖先。
如果 left 和 right 中有一个为 null，那么当前节点的左子树或右子树中必定不存在 p 和 q 的最近公共祖先，因此我们需要返回 left 或 right 中不为 null 的那个节点。
代码
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 root;
}
return left == null ? right : left;
}
}
复杂度分析
时间复杂度：，其中 是二叉树中的节点数。在最坏情况下，我们需要遍历二叉树中的所有节点才能确定最近公共祖先节点。
空间复杂度：，其中 是二叉树中的节点数。空间复杂度主要取决于递归调用的栈空间，最坏情况下，递归调用的栈空间深度为 。
Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal (分治)
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解法
本题考察的是树的遍历和构建。根据前序遍历的顺序我们可以确定根节点，根据中序遍历的顺序我们可以确定左右子树的节点。
以样例为例，根据前序遍历我们可以确定根节点为3，根据中序遍历我们可以确定左子树的节点为[9],右子树的节点为[15,20,7]。然后我们再递归地构建左右子树即可。
代码
class Solution {
private Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(inorder[i], i);
}
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
private TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
int rootVal = preorder[preStart];
int rootIndex = map.get(rootVal);
int leftSize = rootIndex - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root.right = build(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是树中节点的个数。对于每个节点都只访问一次。
空间复杂度：O(n)，其中 n 是树中节点的个数。空间复杂度取决于递归调用的栈深度，栈深度最坏情况下等于树的高度，最好情况下为 logn。
Leetcode 104 Maximum Depth of Binary Tree (回溯 or 分治)
题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
示例 3：
输入：root = [] 输出：0
示例 4：
输入：root = [0] 输出：1
提示：
- 树中节点的数量范围是 [0, 104]
- -100 <= Node.val <= 100
解法
递归求解二叉树的最大深度。如果当前节点为空，则返回深度0；否则，分别递归求解左子树和右子树的最大深度，然后取左右子树深度的最大值加1作为当前节点的深度。
代码
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
复杂度分析
时间复杂度：O(n)，其中n是二叉树的节点数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中height是二叉树的高度。空间复杂度主要取决于递归调用的栈空间，栈空间的大小等于二叉树的高度。平均情况下，二叉树的高度与节点数的对数正相关，空间复杂度为O(logn)。最坏情况下，二叉树退化成链表，空间复杂度为O(n)。
Leetcode 987 Vertical Order Traversal of a Binary Tree
题目描述
给定一个二叉树，返回其节点值的垂直遍历顺序。 即按照列的顺序从上到下，同一列从上到下遍历所有节点。
如果两个节点位置相同，则首先遍历的节点值较小的节点。
每个节点的值保证唯一。
示例 1：
输入: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出:
[ [9], [3,15], [20], [7] ]
示例 2：
输入: [1,2,3,4,5,6,7]
1
/ \
2 3
/ \ / \
4 5 6 7
输出:
[ [4], [2], [1,5,6], [3], [7] ]
解释:
从左到右，每个列分别为：
0 -> 4 1 -> 2 2 -> 1, 5, 6 3 -> 3 4 -> 7
解法
本题的解法是使用哈希表存储每个节点的列号和行号，然后根据列号和行号进行排序，最后按照排序结果输出结果。
具体实现步骤如下：
- 定义哈希表，key为列号，value为List<Pair<Integer, Integer>>类型的列表，其中Pair的第一个元素为该节点的值，第二个元素为该节点的行号。
- 遍历二叉树，使用DFS获取每个节点的列号和行号，存储到哈希表中。
- 根据列号和行号对哈希表进行排序。
- 遍历排序后的哈希表，将每一列的结果存储到List<List>类型的列表中。
- 输出结果。
代码
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
Map<Integer, List<Pair<Integer, Integer>>> map = new HashMap<>();
dfs(root, 0, 0, map);
List<List<Integer>> res = new ArrayList<>();
List<Integer> keys = new ArrayList<>(map.keySet());
Collections.sort(keys);
for (int key : keys) {
List<Pair<Integer, Integer>> list = map.get(key);
Collections.sort(list, (a, b) -> a.getValue() == b.getValue() ? a.getKey() - b.getKey() : a.getValue() - b.getValue());
List<Integer> col = new ArrayList<>();
for (Pair<Integer, Integer> pair : list) {
col.add(pair.getKey());
}
res.add(col);
}
return res;
}
private void dfs(TreeNode node, int col, int row, Map<Integer, List<Pair<Integer, Integer>>> map) {
if (node == null) {
return;
}
List<Pair<Integer, Integer>> list = map.getOrDefault(col, new ArrayList<>());
list.add(new Pair<>(node.val, row));
map.put(col, list);
dfs(node.left, col - 1, row + 1, map);
dfs(node.right, col + 1, row + 1, map);
}
}
复杂度分析
时间复杂度：O(nlogn)，其中n是节点个数。遍历二叉树的时间复杂度是O(n)，对哈希表进行排序的时间复杂度是O(nlogn)。
空间复杂度：O(n)，其中n是节点个数。哈希表存储每个节点的列号和行号，最坏情况下需要存储所有节点的信息。
Leetcode 1485 Clone Binary Tree With Random Pointer
题目描述
给你一个二叉树的根节点 root ，请你设计一个算法来完成以下任务：
1.复制一个和原来的二叉树拥有相同结构相同节点值和相同指向节点的指针，其中拥有相同指向节点的指针指向新的复制的二叉树中的对应节点。
2.随机指向原二叉树节点或者新复制二叉树节点的指针，新复制二叉树中的任何节点都不得指向原二叉树中的节点。
3.请返回新复制二叉树的根节点。
提示：
- 节点数目不超过 1000 。
- 每个节点的值取值范围是 [0, 1000] 。
示例 1：
输入：root = [[1,null],null,[4,3],[7,0]] 输出：[[1,null],null,[4,3],[7,0]] 解释：根节点的值为 1 ，其余节点的值分别为 4、3 和 7 。random 节点指针在图中用绿色表示。
示例 2：
输入：root = [[1,4],null,[1,0],null,[1,5],[1,5]] 输出：[[1,4],null,[1,0],null,[1,5],[1,5]] 解释：节点的值和 random 指针如下所示：
提示：
- 树中节点的数目在范围 [0, 1000] 内
- -1000 <= Node.val <= 1000
- Node.random 为空（null）或指向树中已存在的节点。
解法
本题的解法是使用递归的方式进行二叉树的复制。在复制二叉树的同时，需要保存原二叉树节点和新复制二叉树节点之间的映射关系，以便在随机指针的复制过程中使用。
具体的实现过程如下：
1.首先进行原二叉树节点的复制，并建立原二叉树节点和新复制二叉树节点之间的映射关系。
2.然后再递归进行左右子树的复制，复制过程中需要使用之前建立的映射关系，将原二叉树节点的左右子树映射到新复制二叉树节点的左右子树上。
3.最后递归进行随机指针的复制，复制过程中需要使用之前建立的映射关系，将原二叉树节点的随机指针指向新复制二叉树节点的随机指针。
4.返回新复制二叉树的根节点即可。
代码
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode random;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<TreeNode, TreeNode> map = new HashMap<>();
public TreeNode copyRandomBinaryTree(TreeNode root) {
if (root == null) {
return null;
}
if (map.containsKey(root)) {
return map.get(root);
}
TreeNode node = new TreeNode(root.val);
map.put(root, node);
node.left = copyRandomBinaryTree(root.left);
node.right = copyRandomBinaryTree(root.right);
node.random = copyRandomBinaryTree(root.random);
return node;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树的节点数。需要遍历整棵二叉树进行复制。
空间复杂度：O(n)，其中 n 是二叉树的节点数。需要使用一个哈希表保存原二叉树节点和新复制二叉树节点之间的映射关系。
Leetcode 572 Subtree of Another Tree (分治)
题目描述
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
解法
本题可以通过递归来解决。首先，在树 s 中找到与树 t 根节点值相同的节点，然后递归比较这两个节点是否相同。具体步骤如下：
- 如果树 s 为空，则无法找到与树 t 根节点值相同的节点，返回 false。
- 如果树 s 的根节点值与树 t 的根节点值相同，则调用
isSameTree()方法比较这两个节点是否相同。 - 如果树 s 的根节点值与树 t 的根节点值不同，则递归调用
isSubtree()方法，在树 s 的左子树和右子树中分别查找与树 t 根节点值相同的节点。
在 isSameTree() 方法中，首先判断两个节点是否都为空。如果都为空，则这两个节点相同；如果其中一个为空，则这两个节点不同；如果两个节点都不为空，则比较它们的值是否相同，以及它们的左子树和右子树是否相同。
代码如下：
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
if (isSameTree(s, t)) {
return true;
}
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
复杂度分析
时间复杂度：O(mn)，其中 m 和 n 分别是树 s 和树 t 的节点个数。在最坏情况下，需要遍历树 s 的所有节点，对于每个节点，都需要递归调用 isSameTree() 方法比较其子树与树 t 是否相同，时间复杂度是 O(n)。
空间复杂度：O(max(m, n))，其中 m 和 n 分别是树 s 和树 t 的高度。递归调用 isSameTree() 方法的次数取决于树的高度，空间复杂度是 O(max(m, n))。
Leetcode 863 All Nodes Distance K in Binary Tree
题目描述
给定一个二叉树，一个目标节点和一个整数值 K，求距离该目标节点距离为 K 的所有节点。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 输出：[7,4,1] 解释： 所求结点为与目标结点（值为 5）距离为 2 的结点， 值分别为 7，4，以及 1。
注意，输入的 "root" 和 "target" 实际上是树上的结点。 上面的输入仅仅是对这些对象进行了序列化描述。
提示：
给定的树是非空的，且最多有 K 个结点。 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。 目标结点 target 是树上的结点。 0 <= K <= 1000.
解法
首先，我们需要将二叉树转换成一个邻接表，便于后续的遍历。然后，我们需要进行两次遍历：
第一次遍历：从根节点开始，寻找目标节点，同时记录每个节点的父节点。
第二次遍历：从目标节点开始，进行 BFS 广度优先搜索，将距离目标节点距离为 K 的节点加入结果集中。
具体来说，第一次遍历可以使用 DFS 深度优先搜索实现，第二次遍历则需要使用 BFS 广度优先搜索实现。这里我们使用队列来实现 BFS 遍历，同时需要使用一个 Set 集合来存储已经遍历过的节点，避免重复遍历。
代码
class Solution {
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// 构建邻接表
buildParentMap(root, null);
// BFS
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
queue.offer(target);
visited.add(target);
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
if (distance == k) {
List<Integer> result = new ArrayList<>();
for (TreeNode node : queue) {
result.add(node.val);
}
return result;
}
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (current.left != null && !visited.contains(current.left)) {
visited.add(current.left);
queue.offer(current.left);
}
if (current.right != null && !visited.contains(current.right)) {
visited.add(current.right);
queue.offer(current.right);
}
TreeNode parent = parentMap.get(current);
if (parent != null && !visited.contains(parent)) {
visited.add(parent);
queue.offer(parent);
}
}
distance++;
}
return new ArrayList<>();
}
private void buildParentMap(TreeNode node, TreeNode parent) {
if (node == null) {
return;
}
parentMap.put(node, parent);
buildParentMap(node.left, node);
buildParentMap(node.right, node);
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树中节点的个数。需要进行两次遍历，每次遍历需要遍历所有节点，因此时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树中节点的个数。空间复杂度取决于使用的额外空间，包括邻接表、队列、Set 集合等。邻接表需要 O(n) 的空间，队列和 Set 集合的空间复杂度均为 O(n)。因此总空间复杂度是 O(n)。
Leetcode 1110 Delete Nodes And Return Forest (分治)
题目描述
给定二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，那么从树上删去该节点，你需要返回新树的根节点。
思路：可以通过递归实现。具体来说，对于当前遍历到的节点，若其左子节点在要删除的节点列表中，则将其左子节点置为空，并将其左子节点添加到答案中；若其右子节点在要删除的节点列表中，则将其右子节点置为空，并将其右子节点添加到答案中；最后，若其本身在要删除的节点列表中，则将其左右子节点分别添加到答案中，并返回空。
示例 1：
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出：[[1, 2, null, 4], [6], [7]] 解释：原本的树是这样的，其中 3,5 是要被删除的节点。
输出的三个子树分别是：[1,2,4], [6], [7]。
提示：
树中的节点数最大为 1000。 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。 to_delete.length <= 1000 to_delete 包含一些从 1 到 1000、各不相同的值。
代码
java
class Solution {
List<TreeNode> res = new ArrayList<>();
Set<Integer> set = new HashSet<>();
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
for (int i : to_delete) {
set.add(i);
}
helper(root, true);
return res;
}
private TreeNode helper(TreeNode node, boolean isRoot) {
if (node == null) {
return null;
}
boolean deleted = set.contains(node.val);
if (isRoot && !deleted) {
res.add(node);
}
node.left = helper(node.left, deleted);
node.right = helper(node.right, deleted);
return deleted ? null : node;
}
}
python3
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
res = []
delete_set = set(to_delete)
def dfs(node, is_root):
if not node:
return None
deleted = node.val in delete_set
if is_root and not deleted:
res.append(node)
node.left = dfs(node.left, deleted)
node.right = dfs(node.right, deleted)
return None if deleted else node
dfs(root, True)
return res
复杂度分析
时间复杂度：O(N)，其中 N 是二叉树中的节点个数。
空间复杂度：O(H + K)，其中 H 是二叉树的高度，K 是 to_delete 的长度。空间复杂度主要取决于递归时的栈空间和存储 to_delete 的集合。
Leetcode 230 Kth Smallest element in a BST
题目描述
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
- 树中的节点数为 n 。
- 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
解法
由于是二叉搜索树，中序遍历可以得到递增序列，所以我们可以中序遍历二叉搜索树，得到递增序列，然后返回第 k 个元素。
具体实现上，可以使用递归或者迭代的方式进行中序遍历，并记录已经遍历到的元素个数，当遍历到第 k 个元素时返回即可。
代码
递归
class Solution {
private int count = 0;
private int res = 0;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return res;
}
private void inorder(TreeNode root, int k) {
if (root == null) {
return;
}
inorder(root.left, k);
count++;
if (count == k) {
res = root.val;
return;
}
inorder(root.right, k);
}
}
迭代
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
int count = 0;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
count++;
if (count == k) {
return root.val;
}
root = root.right;
}
return -1;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏情况下，需要遍历所有节点。
空间复杂度：O(n)，其中 n 是二叉搜索树的节点数。空间复杂度主要取决于栈的大小。在最坏情况下，栈的大小为 n，例如二叉搜索树中的所有节点都在一条链上。
Leetcode 98 Validate Binary Search Tree
题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
解法
一棵二叉搜索树的中序遍历结果是一个递增的序列，因此我们可以在中序遍历的过程中判断当前节点的值是否大于前一个节点的值即可。
具体的做法是使用一个指针 prev 记录前一个节点的值，然后在递归遍历左子树时，先判断左子树是否是二叉搜索树，然后再判断当前节点的值是否大于 prev，最后将 prev 更新为当前节点的值。然后递归遍历右子树，重复上述过程即可。
需要注意的是，当遍历到空节点时，我们应该返回 true，因为空节点不影响二叉搜索树的性质。
代码
class Solution {
long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (root.val <= prev) {
return false;
}
prev = root.val;
return isValidBST(root.right);
}
}
复杂度分析
时间复杂度：，其中 是二叉树的节点数。我们需要遍历每个节点恰好一次。
空间复杂度：，其中 是二叉树的高度，递归调用函数的栈空间的大小取决于二叉树的高度。
Leetcode 270 Cloest Binary Search Tree Value
题目描述
给定一个二叉搜索树的根节点 root 和一个目标值 target，找出 BST 中最接近给定目标值的节点值。
注意：本题和 270 https://leetcode-cn.com/problems/closest-binary-search-tree-value/ 相同
示例 1：
输入: root = [4,2,5,1,3], target = 3.714286
输出: 4
示例 2：
输入: root = [1], target = 4.428571
输出: 1
提示：
树中节点总数在范围 [1, 104] 内。 0 <= Node.val <= 109 -109 <= target <= 109
解法
本题可以使用二叉搜索树的性质进行解答。
从根节点开始遍历二叉搜索树，每次遍历到一个节点，比较该节点的值和目标值的差的绝对值与当前最小差的绝对值的大小关系，如果当前节点的值与目标值的差的绝对值更小，则更新当前最小差的绝对值和最小差对应的节点值。然后根据二叉搜索树的性质，如果当前节点的值小于目标值，则遍历当前节点的右子树，否则遍历当前节点的左子树，直到遍历完所有节点。
代码
java
class Solution {
public int closestValue(TreeNode root, double target) {
int closest = root.val;
while (root != null) {
closest = Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
root = root.val < target ? root.right : root.left;
}
return closest;
}
}
python3
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
closest = root.val
while root:
closest = root.val if abs(root.val - target) < abs(closest - target) else closest
root = root.right if root.val < target else root.left
return closest
复杂度分析
时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，树的高度为 n，因此时间复杂度为 O(n)。
空间复杂度：O(1)。只需要维护常量级别的额外空间。
Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
题目描述
给定一个二叉搜索树（BST），找到该树中两个指定节点的最近公共祖先（LCA）。
根据维基百科对最近公共祖先的定义：“两个节点p、q在其最近公共祖先中，当且仅当它们在该树中的子树中，且该节点同时是这两个节点的后代”。
示例 1：
输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出：6 解释：节点 2 和节点 8 的最近公共祖先是 6。
示例 2：
输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出：2 解释：节点 2 和节点 4 的最近公共祖先是 2，因为根据定义最近公共祖先节点可以为节点本身。
提示：
树中节点总数在范围 [2, 105] 内。 -109 <= Node.val <= 109 所有 Node.val 互不相同 。 p != q p 和 q 均存在于 BST 中。
解法
由于二叉搜索树的特性，我们可以根据节点的值大小关系来确定p和q的位置，从而找到它们的最近公共祖先。
当p和q的值都小于根节点的值时，它们的最近公共祖先肯定在根节点的左子树中，递归左子树即可。
当p和q的值都大于根节点的值时，它们的最近公共祖先肯定在根节点的右子树中，递归右子树即可。
当p和q的值一个大于根节点的值，一个小于根节点的值时，此时根节点就是它们的最近公共祖先。
代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
}
复杂度分析
时间复杂度：O(logn)，其中n是树中节点的个数。最坏情况下，树的高度为n，此时时间复杂度为O(n)。
空间复杂度：O(1)。我们只需要常数级别的空间来存储一些变量。
Leetcode 669 Trim a Binary Search Tree (分治)
题目描述
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 1:
输入:
1
/ \
0 2
L = 1
R = 2
输出:
1
\
2
示例 2:
输入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
输出:
3
/
2
/
1
解法
根据二叉搜索树的定义，我们可以发现，如果当前节点的值小于最小边界L，则应该将其右子树作为新的二叉搜索树进行修剪；如果当前节点的值大于最大边界R，则应该将其左子树作为新的二叉搜索树进行修剪；否则，当前节点符合要求，递归处理其左右子树即可。
代码
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return null;
}
if (root.val < L) {
return trimBST(root.right, L, R);
}
if (root.val > R) {
return trimBST(root.left, L, R);
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉搜索树中的节点数。每个节点最多被访问一次。
空间复杂度：O(n)，其中 n 是二叉搜索树中的节点数。空间复杂度主要取决于递归调用的栈空间。
Leetcode 700 Search in a Binary Search Tree
题目描述
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是 5，则应该返回 NULL。
解法
二叉搜索树的特点是：左子树的值小于根节点的值，右子树的值大于根节点的值。因此，我们可以根据目标值与根节点的大小关系，递归地在左子树或右子树中查找目标节点。
具体来说，如果当前节点为空，说明没找到目标节点，返回null；如果当前节点的值等于目标值，说明找到了目标节点，返回当前节点；如果当前节点的值大于目标值，说明目标节点在左子树中，递归地在左子树中查找；如果当前节点的值小于目标值，说明目标节点在右子树中，递归地在右子树中查找。
代码
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (root.val > val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}
}
复杂度分析
时间复杂度：最坏情况下需要遍历整棵树，时间复杂度是 O(n)，其中 n 是树中节点的个数。
空间复杂度：最坏情况下递归调用的层数是树的高度，空间复杂度是 O(h)，其中 h 是树的高度。由于二叉搜索树的特殊性质，当树退化为链表时，树的高度是 n，此时空间复杂度是 O(n)。
Leetcode 108 Convert Sorted Array to Binary Search Tree (分治)
题目描述
给定一个按照升序排列的整数数组 nums，将其转化为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解法
本题要求将一个有序数组转化成一棵高度平衡二叉搜索树。由于该数组是有序的，因此我们可以选取数组的中间元素作为根节点，然后递归地构建左子树和右子树。
具体地，设当前子数组的左右端点为 left 和 right，中间位置为 mid，则中间元素nums[mid] 即为当前子树根节点的值。该根节点左侧的所有元素构成左子树，右侧的所有元素构成右子树。
递归构建左子树和右子树，然后将两棵子树连接到根节点上即可。
代码
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return buildBST(nums, 0, nums.length - 1);
}
private TreeNode buildBST(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildBST(nums, left, mid - 1);
root.right = buildBST(nums, mid + 1, right);
return root;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次，因此时间复杂度为 O(n)。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度为递归调用的深度，根据二叉搜索树的性质，其深度为 O(logn)。平均情况下空间复杂度为 O(logn)，最坏情况下空间复杂度为 O(n)。
Leetcode 333 Largest BST Subtree (与98类似) (分治)
题目描述
给定一个二叉树的根节点 root，找出其中最大的二叉搜索子树，并返回该子树的大小。
二叉搜索树（BST）中的所有节点都具备以下属性：
- 左子树的值小于其父（根）节点的值。
- 右子树的值大于其父（根）节点的值。
- 以此类推，左子树和右子树也都是 BST。
示例 1：
输入：root = [10,5,15,1,8,null,7]
输出：3
解释：本例中，最大的 BST 子树是高亮显示的子树。返回值是子树的大小，即 3 。
示例 2：
输入：root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
输出：2
提示：
- 树上节点数目的范围是 [0, 10^4]
- -10^4 <= Node.val <= 10^4
解法
对于每个节点，我们需要判断它是否为 BST，并计算其大小。如果是 BST，我们比较它的大小和当前最大 BST 的大小，然后更新最大值。为了避免重复计算，我们可以使用一个辅助函数来递归计算每个节点的大小和是否为 BST。
对于每个节点，我们需要比较它的值和左右子树的最大最小值，来判断它是否为 BST。同时，我们需要递归计算左右子树的大小和是否为 BST。
具体实现可以参考代码。
代码
class Solution {
private int maxBSTSize = 0;
public int largestBSTSubtree(TreeNode root) {
if (root == null) {
return 0;
}
isBST(root);
return maxBSTSize;
}
private int[] isBST(TreeNode root) {
if (root == null) {
return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
}
int[] left = isBST(root.left);
int[] right = isBST(root.right);
if (root.val > left[1] && root.val < right[0]) {
int size = left[2] + right[2] + 1;
maxBSTSize = Math.max(maxBSTSize, size);
int min = Math.min(root.val, left[0]);
int max = Math.max(root.val, right[1]);
return new int[]{min, max, size};
} else {
return new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
}
}
}
复杂度分析
时间复杂度：，其中 是二叉树的节点数。我们需要遍历每个节点，每个节点只会被遍历一次。
空间复杂度：，其中 是二叉树的高度。空间复杂度取决于递归调用的栈空间。对于一棵平衡二叉树，。对于一棵不平衡的二叉树， 可以达到 的数量级。
Leetcode 285 Inorder Successor in BST (I, II)
题目描述
给定一个二叉搜索树和其中的一个节点 p ，找到该节点在中序遍历中的后继节点。如果没有后继节点，则返回 null 。
示例 1： 输入：root = [2,1,3], p = 1 输出：2 解释：这里 1 的中序后继节点是 2。请注意 p 和返回值都应是 TreeNode 类型。
示例 2： 输入：root = [5,3,6,2,4,null,null,1], p = 6 输出：null 解释：因为给出的节点没有后继节点，所以答案就返回 null 了。
提示： 树中节点的数目在范围 [1, 10^4] 内。 -10^5 <= Node.val <= 10^5 树中各节点的值均保证唯一。
解法
中序遍历的顺序是 左-根-右，因此在查找p节点的后继节点时，我们需要将当前节点cur看成根节点，如果p节点比cur节点小，那么它的后继节点一定在cur的左子树中，如果p节点比cur节点大，那么它的后继节点一定在cur的右子树中。
如果p节点在cur节点的左子树中，那么cur节点可能是p节点的后继节点或者p节点的后继节点在cur节点的左子树中，因此继续在cur的左子树中寻找p节点的后继节点。
如果p节点在cur节点的右子树中，那么p节点的后继节点一定在cur节点的右子树中，因此继续在cur的右子树中寻找p节点的后继节点。
如果p节点是cur节点，那么p节点的后继节点一定在p节点的右子树中，因此我们需要在p节点的右子树中寻找最左边的节点，即为p节点的后继节点。
代码
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode cur = root;
TreeNode res = null;
while (cur != null) {
if (cur.val > p.val) {
res = cur;
cur = cur.left;
} else {
cur = cur.right;
}
}
return res;
}
}
复杂度分析
时间复杂度：O(h)，其中h是树的高度。在最坏情况下，树呈现链状结构，h=n，时间复杂度为O(n)。在最好情况下，树为完全二叉树，h=logn，时间复杂度为O(logn)。
空间复杂度：O(1)。我们只需要使用常数级别的额外空间。
Leetcode 341 Flatten Nested List Iterator (339 364)
题目描述
给定一个嵌套的整数列表，请你实现一个迭代器来展开它。
实现扁平化嵌套列表类 NestedIterator ：
NestedIterator(List nestedList) 用嵌套列表 nestedList 初始化迭代器。 int next() 返回嵌套列表的下一个整数。 boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。 你的代码将会用下述类型的嵌套列表初始化迭代器：
整数类型，其值只是整数。 列表类型，其中每个元素同样是嵌套的整数列表。
示例 1：
输入：nestedList = [[1,1],2,[1,1]] 输出：[1,1,2,1,1] 解释：通过调用 next 函数直到 hasNext 函数返回 false ， next 函数返回的元素的顺序依次为 [1,1,2,1,1] 。
示例 2：
输入：nestedList = [1,[4,[6]]] 输出：[1,4,6] 解释：通过调用 next 函数直到 hasNext 函数返回 false ， next 函数返回的元素的顺序依次为 [1,4,6] 。
提示：
1 <= nestedList.length <= 500 嵌套列表中的整数值在范围 [-10^6, 10^6] 内
解法
栈。
使用一个栈来存储当前还未遍历的列表，每次调用 next() 函数时，从栈顶弹出一个元素，如果这个元素是一个整数，则直接返回即可；如果是一个列表，则将这个列表展开，并将展开后的元素依次压入栈中。由于栈是后进先出的，因此每次取出的元素就是按深度优先遍历的顺序。
代码
public class NestedIterator implements Iterator<Integer> {
private Stack<NestedInteger> stack;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new Stack<>();
for (int i = nestedList.size() - 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger top = stack.peek();
if (top.isInteger()) {
return true;
}
stack.pop();
List<NestedInteger> list = top.getList();
for (int i = list.size() - 1; i >= 0; i--) {
stack.push(list.get(i));
}
}
return false;
}
}
复杂度分析
时间复杂度：，其中 是嵌套列表中的元素个数。初始化迭代器需要 的时间，每次调用 next() 函数耗时 ，因为每个元素最多被访问一次，而在 hasNext() 函数中，每个元素最多被压入和弹出栈一次，因此总共压入和弹出栈的次数也不会超过 。
空间复杂度：。栈的大小不会超过 ，因为最多同时存储 个列表。
Leetcode 394 Decode String
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此题中，字母可能会被编码多次，例如 "aaa" 可以编码成 "3[a]"。
示例 1：
输入：s = "3[a]2[bc]" 输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]" 输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"
提示：
- 1 <= s.length <= 30
- s 由字母、数字、'['、']'、'.'、'/' 组成
- s 中的字符仅包含数字和字母
解法
本题可以使用栈来模拟字符串的解码过程。遍历字符串，如果当前字符是数字，就将其转换成数字并进栈；如果当前字符是字母或者左括号，直接进栈；如果当前字符是右括号，就开始出栈，直到遇到左括号为止，出栈中的字符就是需要重复的字符串，将其重复 n 次后再次进栈。最后遍历栈中的字符，并将其拼接起来即可。
代码
java
class Solution {
public String decodeString(String s) {
Stack<Integer> numStack = new Stack<>();
Stack<StringBuilder> strStack = new Stack<>();
StringBuilder cur = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + c - '0';
} else if (c == '[') {
numStack.push(num);
strStack.push(cur);
cur = new StringBuilder();
num = 0;
} else if (Character.isLetter(c)) {
cur.append(c);
} else {
StringBuilder tmp = cur;
cur = strStack.pop();
int repeatTimes = numStack.pop();
for (int i = 0; i < repeatTimes; i++) {
cur.append(tmp);
}
num = 0;
}
}
return cur.toString();
}
}
复杂度分析
时间复杂度：O(N)，其中 N 是解码后的字符串长度。
空间复杂度：O(M+N)，其中 M 是栈中元素的数量，N 是解码后的字符串长度。
Leetcode 51 N-Queens (I II基本相同)
题目描述
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每个解决方案包含一个不同的 n 皇后问题的棋子放置方案，其中 'Q' 和 '.' 分别表示一个女王和一个空位置。
示例：
输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示：
- 1 <= n <= 9
- 返回的答案列表中的字符串表示必须要用单引号包括，例如 "Q" -> 'Q'。
解法
本题是一个典型的回溯算法问题。我们从第一行开始，枚举每列是否可以放置皇后，如果可以，则继续往下一行递归。如果不能放置，则回溯到上一行，继续尝试下一列。直到所有的行都放置好皇后，得到一个解法。
在判断某个位置是否可以放置皇后时，需要判断该位置所在的行、列、两条对角线上是否有其他皇后。可以使用三个 boolean 数组来记录某一列、两条对角线上是否已经有皇后。具体实现详见代码注释。
代码
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
boolean[] col = new boolean[n]; // 记录某一列是否已经放置了皇后
boolean[] diag1 = new boolean[2 * n - 1]; // 记录主对角线是否已经放置了皇后
boolean[] diag2 = new boolean[2 * n - 1]; // 记录副对角线是否已经放置了皇后
char[][] board = new char[n][n]; // 棋盘
// 初始化棋盘
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
dfs(res, board, col, diag1, diag2, 0, n);
return res;
}
private void dfs(List<List<String>> res, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2, int row, int n) {
if (row == n) { // 找到一组解法
List<String> solution = new ArrayList<>();
for (int i = 0; i < n; i++) {
solution.add(new String(board[i]));
}
res.add(solution);
return;
}
for (int j = 0; j < n; j++) {
if (!col[j] && !diag1[row + j] && !diag2[row - j + n - 1]) { // 判断该位置是否可以放置皇后
board[row][j] = 'Q';
col[j] = true;
diag1[row + j] = true;
diag2[row - j + n - 1] = true;
dfs(res, board, col, diag1, diag2, row + 1, n); // 继续递归下一行
board[row][j] = '.';
col[j] = false;
diag1[row + j] = false;
diag2[row - j + n - 1] = false;
}
}
}
}
复杂度分析
时间复杂度：，其中 是棋盘的大小。最坏情况下，需要枚举所有 种放置皇后的方案，时间复杂度为 。
空间复杂度：，其中 是棋盘的大小。需要使用 的空间存储棋盘和三个 boolean 数组。
Leetcode 291 Word Pattern II (I为简单的Hashmap题)
题目描述
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例 1:
输入: pattern = "abab", str = "redblueredblue" 输出: true
示例 2:
输入: pattern = "aaaa", str = "asdasdasdasd" 输出: true
示例 3:
输入: pattern = "aabb", str = "xyzabcxzyabc" 输出: false
说明:
你可以默认 pattern 和 str 都只会包含小写字母。
解法
本题可以使用回溯算法进行解决。我们可以使用一个哈希表来存储已经匹配的字符和字符串的映射关系，同时使用一个 HashSet 来存储已经匹配过的字符串，避免重复匹配。
在回溯算法的过程中，我们从 pattern 字符串的第一个字符开始，尝试匹配所有可能的字符串。如果当前字符已经在哈希表中出现过了，就尝试使用哈希表中对应的字符串进行匹配；否则，我们从当前位置开始，尝试匹配所有可能的字符串。
在匹配成功后，我们需要将当前字符和字符串的映射关系存入哈希表中，并且将当前字符串加入 HashSet 中。接着，我们递归处理下一个字符和字符串。如果递归过程中出现不匹配的情况，就需要回溯到上一个状态，重新尝试其他的匹配方式。
代码
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
return helper(pattern, str, map, set);
}
private boolean helper(String pattern, String str, Map<Character, String> map, Set<String> set) {
if (pattern.length() == 0) {
return str.length() == 0;
}
char c = pattern.charAt(0);
if (map.containsKey(c)) {
String s = map.get(c);
if (!str.startsWith(s)) {
return false;
}
return helper(pattern.substring(1), str.substring(s.length()), map, set);
}
for (int i = 0; i < str.length(); i++) {
String s = str.substring(0, i + 1);
if (set.contains(s)) {
continue;
}
map.put(c, s);
set.add(s);
if (helper(pattern.substring(1), str.substring(i + 1), map, set)) {
return true;
}
map.remove(c);
set.remove(s);
}
return false;
}
}
复杂度分析
时间复杂度：，其中 是字符串 str 的长度， 是 pattern 字符串的长度。在回溯算法的过程中，我们需要尝试所有可能的字符串匹配方式，因此时间复杂度是指数级别的。
空间复杂度：，其中 是 pattern 字符串的长度。在回溯算法的过程中，我们需要使用哈希表和 HashSet 来存储已经匹配的字符和字符串的映射关系，因此空间复杂度是常数级别的。
Leetcode 126 Word Ladder II （I为BFS题目）
题目描述
给定两个单词（beginWord 和 endWord）和一个字典，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换后得到的新单词必须在字典中存在。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
解法
本题可以使用BFS来解决，先将所有单词存入一个set中，然后从beginWord开始，逐个改变单词中的每一个字符，如果改变后的单词在set中，就将其加入队列中。为了记录每个单词的前驱单词，可以使用一个Map来记录。当队列为空时，说明已经找到了所有的最短转换序列，可以通过回溯的方式将所有路径找出来。
代码
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
return new ArrayList<>();
}
// 记录每个单词的前驱单词
Map<String, List<String>> preMap = new HashMap<>();
// 记录每个单词到beginWord的最短距离
Map<String, Integer> distanceMap = new HashMap<>();
// BFS队列
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
distanceMap.put(beginWord, 0);
while (!queue.isEmpty()) {
int size = queue.size();
boolean foundEndWord = false;
Set<String> visitedSet = new HashSet<>();
for (int i = 0; i < size; i++) {
String curWord = queue.poll();
char[] wordArray = curWord.toCharArray();
for (int j = 0; j < wordArray.length; j++) {
char originalChar = wordArray[j];
for (char k = 'a'; k <= 'z'; k++) {
if (originalChar == k) {
continue;
}
wordArray[j] = k;
String newWord = new String(wordArray);
if (wordSet.contains(newWord)) {
if (newWord.equals(endWord)) {
foundEndWord = true;
}
if (!visitedSet.contains(newWord)) {
queue.offer(newWord);
visitedSet.add(newWord);
}
// 更新前驱单词
preMap.computeIfAbsent(newWord, k1 -> new ArrayList<>()).add(curWord);
// 更新到beginWord的距离
distanceMap.put(newWord, distanceMap.get(curWord) + 1);
}
}
wordArray[j] = originalChar;
}
}
if (foundEndWord) {
break;
}
}
List<List<String>> res = new ArrayList<>();
if (!preMap.containsKey(endWord)) {
return res;
}
List<String> path = new ArrayList<>();
path.add(endWord);
backtrack(endWord, beginWord, preMap, path, res, distanceMap);
return res;
}
private void backtrack(String curWord, String beginWord, Map<String, List<String>> preMap, List<String> path, List<List<String>> res, Map<String, Integer> distanceMap) {
if (curWord.equals(beginWord)) {
List<String> tempPath = new ArrayList<>(path);
Collections.reverse(tempPath);
res.add(tempPath);
return;
}
for (String preWord : preMap.get(curWord)) {
if (distanceMap.get(preWord) + 1 == distanceMap.get(curWord)) {
path.add(preWord);
backtrack(preWord, beginWord, preMap, path, res, distanceMap);
path.remove(path.size() - 1);
}
}
}
}
复杂度分析
时间复杂度：O(M ^ 2 * N)，其中 M 是单词的长度，N 是单词表中单词的个数。预处理的时间复杂度是 O(M * N)，BFS的时间复杂度是 O(M ^ 2 * N)，回溯的时间复杂度是 O(N * L)，其中 L 是所有最短转换序列的长度之和。
空间复杂度：O(M * N)，其中 M 是单词的长度，N 是单词表中单词的个数。需要使用一个Map来记录每个单词的前驱单词，空间复杂度是 O(N * M)；需要使用一个Map来记录每个单词到beginWord的最短距离，空间复杂度是 O(N * M)；需要使用一个List来记录所有的最短转换序列，空间复杂度是 O(N * L)。
Leetcode 93 Restore IP Addresses
题目描述
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能包含前导 0），整数之间用 '.' 分隔。
例如： "0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000
s 仅由数字组成
解法
本题可以使用回溯算法来解决。回溯算法的过程就是不断枚举所有可能的解，直到找到符合条件的解或者所有解都枚举完了，这个过程中需要使用剪枝来减少不必要的枚举。
对于每一个可以成为 IP 地址的数字，我们可以将其分成 13 段，每一段的数字必须在 0255 之间，且不能包含前导 0。
我们可以使用一个数组来存储当前已经处理的数字，以及已经分割好的段数。在回溯的过程中，如果已经处理的数字个数为 4，且所有数字都已经被处理完了，那么就找到了一种符合条件的 IP 地址，将其加入结果数组中。否则，我们需要继续枚举下一个数字，并判断其是否可以成为 IP 地址的一段。
需要注意的是，如果当前的数字已经超过了字符串的长度，那么就不能继续分割，需要进行回溯。
代码
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) {
return res;
}
int[] nums = new int[4];
dfs(s, 0, 0, nums, res);
return res;
}
private void dfs(String s, int start, int count, int[] nums, List<String> res) {
if (count == 4 && start == s.length()) {
res.add(nums[0] + "." + nums[1] + "." + nums[2] + "." + nums[3]);
return;
}
if (count == 4 || start == s.length()) {
return;
}
int num = 0;
for (int i = start; i < s.length(); i++) {
num = num * 10 + (s.charAt(i) - '0');
if (num > 255) {
break;
}
nums[count] = num;
dfs(s, i + 1, count + 1, nums, res);
if (num == 0) {
break;
}
}
}
}
复杂度分析
时间复杂度：，其中 表示每个数字可以分成 ~ 段， 表示一共需要分割 段。
空间复杂度：，因为只需要使用常数级别的额外空间来存储已经处理好的数字和分割好的段数。
Leetcode 22 Generate Parentheses
题目描述
给定一个数 n，生成所有由 n 对括号组成的组合。
示例 1:
输入: 3
输出:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解法
本题可以使用回溯法进行求解。回溯法的基本思路是在解空间树中搜索问题的解，对于每个搜索到的节点，判断是否满足问题的要求，如果满足要求则继续向下搜索，否则剪枝。
对于本题，我们可以用 left 和 right 分别表示当前左括号和右括号的数量，初始值均为 0。在搜索过程中，每次可以选择添加一个左括号或者一个右括号，添加左括号的条件是 left < n，添加右括号的条件是 right < left。如果 left 和 right 均等于 n，则表示已经找到了一个合法的括号序列，将其加入结果列表中即可。
代码
java
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, new StringBuilder(), 0, 0, n);
return res;
}
private void backtrack(List<String> res, StringBuilder sb, int left, int right, int n) {
if (left == n && right == n) {
res.add(sb.toString());
return;
}
if (left < n) {
sb.append("(");
backtrack(res, sb, left + 1, right, n);
sb.deleteCharAt(sb.length() - 1);
}
if (right < left) {
sb.append(")");
backtrack(res, sb, left, right + 1, n);
sb.deleteCharAt(sb.length() - 1);
}
}
}
复杂度分析
时间复杂度：在最坏情况下，需要枚举所有的括号序列，时间复杂度为 O(2^{2n})。
空间复杂度：使用了递归栈空间，空间复杂度为 O(n)。
Leetcode 586 Score of Parentheses
题目描述
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。 AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()" 输出： 1 示例 2：
输入： "(())" 输出： 2 示例 3：
输入： "()()" 输出： 2 示例 4：
输入： "(()(()))" 输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。 2 <= S.length <= 50
解法
本题可以使用栈来解决，遍历字符串，当遇到左括号时，将其入栈，当遇到右括号时，先弹出栈顶元素，如果弹出的是左括号，则说明这是一个()，得1分，否则说明这是一个(A)，得2*A分，然后再将得分入栈，最后将所有得分相加即可。
代码如下：
class Solution {
public int scoreOfParentheses(String S) {
Stack<Integer> stack = new Stack<>();
for (char c : S.toCharArray()) {
if (c == '(') {
stack.push(0);
} else {
int score = stack.pop();
stack.peek();
if (score == 0) {
stack.push(1);
} else {
stack.push(2 * score);
}
int sum = 0;
while (!stack.isEmpty() && stack.peek() != 0) {
sum += stack.pop();
}
stack.push(sum);
}
}
return stack.pop();
}
}
复杂度分析
时间复杂度：，其中 是字符串的长度，需要遍历整个字符串。
空间复杂度：，需要使用栈来存储得分，最坏情况下栈的大小为字符串的长度。
Leetcode 301 Remove Invalid Parentheses
题目描述
给定一个只包含 '(' 和 ')' 的字符串，删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 '(' 和 ')' 以外的字符。
示例 1:
输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:
输入: ")("
输出: [""]
解法
本题可以使用BFS来解决。我们将初始字符串加入队列中，然后依次枚举每个字符，如果当前字符是左括号或右括号，我们都尝试删除它，然后将新的字符串加入队列中。如果已经找到了有效的括号字符串，我们就不再加入队列中了。
为了避免重复计算，我们使用一个哈希表来记录已经加入队列的字符串。如果当前字符串已经在哈希表中出现过了，我们就不再加入队列中了。
代码
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if (s == null) {
return res;
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
String cur = queue.poll();
if (isValid(cur)) {
res.add(cur);
found = true;
}
if (found) {
continue;
}
for (int i = 0; i < cur.length(); i++) {
char c = cur.charAt(i);
if (c != '(' && c != ')') {
continue;
}
String next = cur.substring(0, i) + cur.substring(i + 1);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return res;
}
private boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
count++;
} else if (c == ')') {
count--;
if (count < 0) {
return false;
}
}
}
return count == 0;
}
}
复杂度分析
时间复杂度：O(2^n)，其中 n 是字符串的长度。每个字符都有两种可能，要么删除，要么不删除，因此一共有 2^n 种可能的字符串。
空间复杂度：O(n)，其中 n 是字符串的长度。我们需要使用哈希表和队列来存储字符串。
Leetcode 37 Sodoku Solver
题目描述
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出:
[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]
解释: 输入的数独如上图所示，唯一有效的解决方案如下所示：
提示:
给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。
解法
本题解法采用回溯法。
对于数独中的每一个未填数字的位置，我们依次尝试填入1-9中的数字，如果填入的数字符合数独规则，则继续填下一个未填的位置，否则将当前位置还原为'.'，回溯到上一个位置，继续尝试填入下一个数字。
为了方便检查数独规则，我们可以先预处理出每行、每列、每个3x3的宫内已经填入的数字，然后在填数字时进行检查。
代码
class Solution {
public void solveSudoku(char[][] board) {
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][] boxUsed = new boolean[9][10];
// 预处理已经填入的数字
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0';
rowUsed[i][num] = true;
colUsed[j][num] = true;
boxUsed[i / 3 * 3 + j / 3][num] = true;
}
}
}
backtrack(board, rowUsed, colUsed, boxUsed, 0, 0);
}
private boolean backtrack(char[][] board, boolean[][] rowUsed, boolean[][] colUsed, boolean[][] boxUsed, int row, int col) {
if (col == 9) {
col = 0;
row++;
if (row == 9) {
return true;
}
}
if (board[row][col] == '.') {
for (int num = 1; num <= 9; num++) {
if (!rowUsed[row][num] && !colUsed[col][num] && !boxUsed[row / 3 * 3 + col / 3][num]) {
board[row][col] = (char) (num + '0');
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row / 3 * 3 + col / 3][num] = true;
if (backtrack(board, rowUsed, colUsed, boxUsed, row, col + 1)) {
return true;
}
board[row][col] = '.';
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row / 3 * 3 + col / 3][num] = false;
}
}
} else {
return backtrack(board, rowUsed, colUsed, boxUsed, row, col + 1);
}
return false;
}
}
复杂度分析
时间复杂度：O(9^m)，其中 m 是数独中空白格的个数。最坏情况下，需要尝试填入 9 种数字，每个空白格最多需要填入 m 次，因此总时间复杂度为 O(9^m)。
空间复杂度：O(1)。需要使用常数个额外空间。
Leetcode 212 Word Search II （I, II）
题目描述
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
word = "oath"
输出: true
解法
本题可以使用深度优先搜索（DFS）+回溯的方法来解决。
我们从网格的每一个位置出发，如果当前位置的字符和单词的第一个字符相同，就从这个位置开始进行深度优先搜索。在搜索的过程中，如果发现当前字符和单词中对应的字符不同，或者已经访问过了当前位置，就需要回溯到上一个位置进行搜索。
具体来说，我们可以先遍历整个网格，找到和单词的第一个字符相同的位置，然后从这些位置开始进行深度优先搜索。在搜索的过程中，我们需要记录已经访问过的位置，在搜索完成后需要将其状态回溯。
代码
class Solution {
private int m, n;
private boolean[][] visited;
private int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
m = board.length;
n = board[0].length;
visited = new boolean[m][n];
for (String word : words) {
boolean flag = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, word, i, j, 0)) {
res.add(word);
flag = true;
break;
}
}
}
if (flag) {
break;
}
}
}
return res;
}
private boolean dfs(char[][] board, String word, int i, int j, int k) {
if (k == word.length() - 1) {
return board[i][j] == word.charAt(k);
}
if (board[i][j] == word.charAt(k)) {
visited[i][j] = true;
for (int[] direction : directions) {
int newi = i + direction[0], newj = j + direction[1];
if (newi >= 0 && newi < m && newj >= 0 && newj < n && !visited[newi][newj]) {
if (dfs(board, word, newi, newj, k + 1)) {
return true;
}
}
}
visited[i][j] = false;
}
return false;
}
}
复杂度分析
时间复杂度：，其中 是网格的行数， 是网格的列数， 是单词的平均长度。在最坏情况下，需要遍历整个网格，时间复杂度为 。
空间复杂度：。需要使用额外的空间记录已经访问过的位置。
Leetcode 1087 Brace Expansion
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
解法
本题解法是使用栈来实现基本计算器的计算过程。对于每个字符，有以下几种情况：
- 如果是数字，则一直读取到数字结束，将数字加入到栈中；
- 如果是运算符，则将其加入到栈中；
- 如果是左括号，则将其加入到栈中；
- 如果是右括号，则将栈顶的元素一直出栈，直到遇到左括号为止，并将计算结果加入到栈中。
最后将栈中的所有元素相加即可得到结果。
代码
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0, res = 0, sign = 1;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+') {
res += sign * num;
num = 0;
sign = 1;
} else if (c == '-') {
res += sign * num;
num = 0;
sign = -1;
} else if (c == '(') {
stack.push(res);
stack.push(sign);
res = 0;
sign = 1;
} else if (c == ')') {
res += sign * num;
num = 0;
res *= stack.pop();
res += stack.pop();
}
}
if (num != 0) {
res += sign * num;
}
return res;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串 s 一次。
空间复杂度：O(n)，其中 n 是字符串 s 的长度。最坏情况下，栈中会存储所有的数字和运算符。
Leetcode 399 Evaluate Division
题目描述
给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
示例 1:
输入:
a = [["a", "b"], ["b", "c"]]
b = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
输出: [6.00000, 0.50000, -1.00000, 1.00000, -1.00000 ]
解释:
给定：a / b = 2.0, b / c = 3.0
问题 1：a / c = ?, 结果为 2.0 * 3.0 = 6.00000
问题 2：b / a = ?, 结果为 0.5 = 1/2
问题 3：a / e = ?, 结果为 -1.0
问题 4：a / a = ?, 结果为 1.0
问题 5：x / x = ?, 结果为 -1.0
注意:
输入中的所有字符串均为非空字符串，且长度不超过 10。 输入中的数字均为非零数字，且范围为 [-30, 30]。 答案保留 5 位小数，即便是很接近的整数也会被视为错误的答案。
解法
本题可以使用图的遍历来求解。首先将给定的变量和浮点数建立一个有向图，其中变量作为节点，浮点数作为边的权重。然后对于每个查询，使用深度优先搜索来遍历图，从起点到终点的路径上的权重之积即为答案。如果起点或终点不存在于图中，或者无法从起点到达终点，则答案为 -1.0。
具体来说，我们可以先将所有的变量和浮点数存储在一个哈希表中，然后遍历 a 数组，对于每个方程式 A / B = k，将 A 和 B 作为图中的两个节点，建立一条从 A 指向 B 的边，权重为 k。然后对于每个查询，使用深度优先搜索来遍历图，从起点到终点的路径上的权重之积即为答案。
代码
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
// 存储所有变量及其对应的编号
Map<String, Integer> map = new HashMap<>();
int idx = 0;
for (List<String> equation : equations) {
String a = equation.get(0);
String b = equation.get(1);
if (!map.containsKey(a)) {
map.put(a, idx++);
}
if (!map.containsKey(b)) {
map.put(b, idx++);
}
}
// 构建有向图
double[][] graph = new double[idx][idx];
for (int i = 0; i < equations.size(); i++) {
String a = equations.get(i).get(0);
String b = equations.get(i).get(1);
int x = map.get(a);
int y = map.get(b);
double val = values[i];
graph[x][y] = val;
graph[y][x] = 1.0 / val;
}
// 对每个查询进行深度优先搜索
double[] res = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
String a = queries.get(i).get(0);
String b = queries.get(i).get(1);
if (!map.containsKey(a) || !map.containsKey(b)) {
res[i] = -1.0;
} else {
int x = map.get(a);
int y = map.get(b);
boolean[] visited = new boolean[idx];
res[i] = dfs(graph, x, y, visited, 1.0);
if (res[i] == 0.0) {
res[i] = -1.0;
}
}
}
return res;
}
private double dfs(double[][] graph, int x, int y, boolean[] visited, double val) {
if (x == y) {
return val;
}
visited[x] = true;
for (int i = 0; i < graph.length; i++) {
if (graph[x][i] != 0.0 && !visited[i]) {
double res = dfs(graph, i, y, visited, val * graph[x][i]);
if (res != 0.0) {
return res;
}
}
}
return 0.0;
}
}
复杂度分析
时间复杂度：，其中 是变量的数量， 是方程式的数量， 是查询的数量。建图的时间复杂度为 ，对于每个查询，需要进行一次深度优先搜索，时间复杂度为 。因此总时间复杂度为 。在深度优先搜索中，访问每个节点最多一次，因此可以使用一个布尔数组来记录节点是否被访问过，空间复杂度为 。
空间复杂度：。需要使用哈希表存储每个变量及其对应的编号，空间复杂度为 。需要使用一个二维数组存储图的邻接矩阵，空间复杂度为 。对于每个查询，需要使用一个布尔数组来记录节点是否被访问过，空间复杂度为 。因此总空间复杂度为 。
Leetcode 1274 Number of Ships in a Rectangle
题目描述
在一个二维的平面空间中，所有的点都用整数坐标来表示。现在，我们有一些点 (x, y)，请你来判断是否存在两个点在平面上构成一个矩形，该矩形由两条平行于坐标轴的线段和两条平行于坐标轴的线段组成。
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
解释：这些点如下图所示。
其中红色矩形是我们所求的矩形，它包含了 4 个黄色的点。
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
提示：
- 1 <= points.length <= 500
- 0 <= points[i][0] <= 40000
- 0 <= points[i][1] <= 40000
- 所有的点都是不同的。
解法
本题的解法是使用哈希表和二分查找。我们遍历每两个点，如果这两个点的横坐标和纵坐标都不相等，那么这两个点就可以构成一个矩形。我们可以将这个矩形的左上角和右下角的坐标存储到哈希表中。我们可以使用一个哈希表，键是一个二元组 (x, y)，值是一个整数，表示有多少个点是以这个二元组为左上角的矩形的右下角。
我们遍历每个点，对于每个点，我们在哈希表中查找有多少个以这个点为右下角的矩形。我们可以使用二分查找，在哈希表中查找左上角坐标小于当前点的所有矩形的数量。这样，我们就可以得到以当前点为右下角的矩形的数量，然后将这个数量加入到哈希表中以当前点为右下角的矩形的数量中。
代码
class Solution {
public int countShips(int[][] sea, int[] topRight, int[] bottomLeft) {
Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();
for (int[] point : sea) {
if (point[0] > topRight[0] || point[1] > topRight[1] || point[0] < bottomLeft[0] || point[1] < bottomLeft[1]) {
continue;
}
Pair<Integer, Integer> p = new Pair<>(point[0], point[1]);
map.put(p, map.getOrDefault(p, 0) + 1);
}
int ans = 0;
for (int[] point : sea) {
if (point[0] > topRight[0] || point[1] > topRight[1] || point[0] < bottomLeft[0] || point[1] < bottomLeft[1]) {
continue;
}
Pair<Integer, Integer> p = new Pair<>(point[0], point[1]);
int count = map.get(p);
Pair<Integer, Integer> p1 = new Pair<>(bottomLeft[0], bottomLeft[1]);
Pair<Integer, Integer> p2 = new Pair<>(topRight[0], topRight[1]);
ans += countRectangles(map, p1, p, count) * countRectangles(map, p, p2, count);
map.put(p, map.get(p) - 1);
}
return ans;
}
private int countRectangles(Map<Pair<Integer, Integer>, Integer> map, Pair<Integer, Integer> p1, Pair<Integer, Integer> p2, int count) {
int x1 = p1.getKey(), y1 = p1.getValue(), x2 = p2.getKey(), y2 = p2.getValue();
Pair<Integer, Integer> p3 = new Pair<>(x1, y2);
Pair<Integer, Integer> p4 = new Pair<>(x2, y1);
int count1 = countRectangles(map, p1, p3);
int count2 = countRectangles(map, p3, p4);
int count3 = countRectangles(map, p4, p2);
return count1 * count2 * count3 * count;
}
private int countRectangles(Map<Pair<Integer, Integer>, Integer> map, Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
int x1 = p1.getKey(), y1 = p1.getValue(), x2 = p2.getKey(), y2 = p2.getValue();
if (x1 >= x2 || y1 >= y2) {
return 0;
}
Pair<Integer, Integer> p3 = new Pair<>(x1, y2);
Pair<Integer, Integer> p4 = new Pair<>(x2, y1);
int count1 = countRectangles(map, p1, p3);
int count2 = countRectangles(map, p3, p4);
int count3 = countRectangles(map, p4, p2);
int count4 = map.getOrDefault(p2, 0) - map.getOrDefault(p3, 0)
- map.getOrDefault(p4, 0) + map.getOrDefault(p1, 0);
return count1 * count2 * count3 * count4 + count1 * count2 + count1 * count3 + count2 * count3;
}
}
复杂度分析
时间复杂度：O(n^2 log n)，其中n是点的数量。我们需要遍历每两个点，因此时间复杂度是O(n^2)。对于每个点，我们需要在哈希表中进行二分查找，因此时间复杂度是O(log n)。由于我们需要遍历每个点，因此总时间复杂度是O(n^2 log n)。
空间复杂度：O(n)，其中n是点的数量。我们需要使用一个哈希表来存储每个点，因此空间复杂度是O(n)。
Leetcode 1376 Time Needed to Inform All Employees
题目描述
公司里有 n 名员工，他们的 ID 从 0 到 n - 1。给定数组 manager，其中 manager[i] 是第 i 名员工的经理。对于每个员工，他们都有一个工作时间 startTime 和一个工作时间结束时间 endTime，他们都是从 严格的时间点 开始工作的。
每个员工从 startTime 开始工作，并一直工作到 endTime 结束。员工们每个人都会属于一个组，总共有 m 个组。在他们的工作时间内，每个员工都有可能需要与同组的其他人或者其他组的人进行通信。
通信需要遵循一些规则：
如果正在通信的两名员工不属于同一组，则必须通过他们的经理进行传递。经理传递信息是不受时间限制的 如果两名属于同一组的员工正在通信，则它们可以在他们的工作时间中的任何时候进行通信 对于属于同一组的员工，他们的 startTime 和 endTime 会被统计为通信时间。所以即使他们没有通信，他们也必须在这段时间内待在同一处。可以看出，你可以选择将任何员工放在一个组或者独自一组。
你的任务是计算并返回所有这些员工在工作时间内能够完成的唯一通信时间总数。
示例 1：
输入：n = 1, manager = [-1], informTime = [0], startTime = [0], endTime = [0]
输出：0
解释：无论如何，该员工都没有可以通信的同事。
示例 2：
输入：n = 6, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0], startTime = [1,2,3,4,5,6], endTime = [2,3,4,5,6,7]
输出：1
解释：根据输入，员工 0 和 1 不在同一组，所以必须通过他们的经理来进行通信。经理可以在不受时间限制的情况下传递信息。其他员工都在同一组，可以直接进行通信。
示例 3：
输入：n = 7, manager = [1,2,3,4,5,6,-1], informTime = [0,6,0,0,0,0,0], startTime = [1,2,3,4,5,6,7], endTime = [2,3,4,5,6,7,8]
输出：21
解释：根据输入，员工 2 和 3 在同一组，会在 3 秒时进行通信。员工 3 和 4 在同一组，会在 4 秒时进行通信。员工 4 和 5 在同一组，会在 5 秒时进行通信。
提示：
1 <= n <= 10^5
0 <= manager[i] < n
manager[0] == -1 表示编号为 0 的员工是公司的最高管理者。
informTime.length == n
0 <= informTime[i] <= 1000
1 <= startTime[i] < endTime[i] <= 10^9
每个员工都有一个唯一的 ID 。
解法
题目要求我们计算所有员工在工作时间内能够完成的唯一通信时间总数，我们可以采用深度优先搜索（DFS）的方法来解决这个问题。我们从最高管理者开始遍历整个公司，对于每个员工，我们记录他到最高管理者的通信时间，然后递归遍历他的下属员工，将他们的通信时间更新为当前员工到最高管理者的通信时间加上传递给他们的时间，最后返回所有员工的最大通信时间即可。
具体实现时，我们可以使用一个哈希表来记录每个员工的下属员工，这样在递归遍历时就不需要每次都遍历整个员工列表了。
代码
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
Map<Integer, List<Integer>> subordinates = new HashMap<>();
for (int i = 0; i < n; i++) {
if (i == headID) {
continue;
}
int managerId = manager[i];
if (!subordinates.containsKey(managerId)) {
subordinates.put(managerId, new ArrayList<>());
}
subordinates.get(managerId).add(i);
}
return dfs(headID, subordinates, informTime);
}
private int dfs(int curEmployee, Map<Integer, List<Integer>> subordinates, int[] informTime) {
if (!subordinates.containsKey(curEmployee)) {
return 0;
}
int maxTime = 0;
for (int subordinate : subordinates.get(curEmployee)) {
maxTime = Math.max(maxTime, dfs(subordinate, subordinates, informTime));
}
return maxTime + informTime[curEmployee];
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是员工的数量。我们需要遍历每个员工一次，并且对于每个员工，我们需要遍历他的下属员工，时间复杂度为 O(n)。
空间复杂度：O(n)，其中 n 是员工的数量。我们需要使用哈希表来存储每个员工的下属员工，空间复杂度为 O(n)。
Leetcode 694 Number of Distinct Islands
题目描述
给定一个由 0 和 1 组成的二维网格，求不同岛屿的数量。
岛屿是由四个方向（水平或竖直）相邻的 1 （代表土地）形成的组。你可以假设网格的四个边缘都被水包围着。
示例 1:
11000 11000 00011 00011
给定上面的网格，返回结果 1 。
示例 2:
11011 10000 00001 11011
给定上面的网格，返回结果 3 。
注意:
11 1
和
1 11
被认为是不同的岛屿，因为我们不考虑岛屿的旋转和翻折。
解法
本题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）进行求解。
具体做法是，遍历整个网格，对于每个遇到的 1，进行深度或广度优先搜索，将与其相邻的 1 都标记为已访问，然后将该岛屿的形状进行记录。最后将所有不同的岛屿形状进行统计即可。
需要注意的是，在进行深度或广度优先搜索时，需要记录每个岛屿的起点位置，以便后面进行岛屿形状的记录。
代码中使用了 HashSet 来记录不同的岛屿形状，使用了 StringBuilder 来记录每个岛屿的形状。DFS 和 BFS 的实现细节略有不同，具体见代码注释。
代码
DFS
class Solution {
public int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<String> set = new HashSet<>(); // 记录不同的岛屿形状
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
StringBuilder sb = new StringBuilder();
dfs(grid, i, j, i, j, sb); // 对该岛屿进行深度优先搜索
set.add(sb.toString()); // 将该岛屿的形状加入集合中
}
}
}
return set.size();
}
private void dfs(int[][] grid, int i0, int j0, int i, int j, StringBuilder sb) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
return;
}
grid[i][j] = 0; // 标记为已访问
sb.append(i - i0).append(j - j0); // 记录该点的相对位置
dfs(grid, i0, j0, i - 1, j, sb); // 上
dfs(grid, i0, j0, i + 1, j, sb); // 下
dfs(grid, i0, j0, i, j - 1, sb); // 左
dfs(grid, i0, j0, i, j + 1, sb); // 右
}
}
BFS
class Solution {
public int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<String> set = new HashSet<>(); // 记录不同的岛屿形状
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
StringBuilder sb = new StringBuilder();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = 0; // 标记为已访问
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int ni = cur[0] + dir[0], nj = cur[1] + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
grid[ni][nj] = 0; // 标记为已访问
sb.append(ni - i).append(nj - j); // 记录该点的相对位置
queue.offer(new int[]{ni, nj});
}
}
}
set.add(sb.toString()); // 将该岛屿的形状加入集合中
}
}
}
return set.size();
}
}
复杂度分析
时间复杂度：，其中 和 分别是网格的行数和列数。需要遍历整个网格，对于每个岛屿需要进行深度或广度优先搜索，时间复杂度均为 。
空间复杂度：。使用了额外的空间记录已访问的网格和岛屿形状。对于 DFS 实现，使用了 StringBuilder 记录每个岛屿的形状，StringBuilder 的长度不超过 ，因此空间复杂度为 。对于 BFS 实现，使用了队列记录每个岛屿的位置，队列的大小不超过 ，因此空间复杂度为 。
Leetcode 131 Palindrome Partitioning
题目描述
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
解法
本题可以使用回溯算法进行求解。回溯算法的基本思路是枚举所有可能的情况，然后进行判断和剪枝，最终得到符合要求的结果。
在本题中，我们需要枚举所有可能的分割方案。对于每个分割方案，我们需要判断每个子串是否是回文串。如果是回文串，我们就可以继续递归下去，否则就需要剪枝，回溯到上一个状态。
具体实现时，我们可以使用一个列表来存储当前分割方案，然后使用两个指针 i 和 j 来枚举子串的起始位置和结束位置。如果当前子串是回文串，我们就将其加入到列表中，并递归处理剩下的部分。如果当前子串不是回文串，我们就直接进行回溯。
代码
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
backtrack(s, 0, path, res);
return res;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
String sub = s.substring(start, i + 1);
if (isPalindrome(sub)) {
path.add(sub);
backtrack(s, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
复杂度分析
时间复杂度：O(n * 2^n)，其中 n 是字符串的长度。对于每个位置，我们可以选择将其作为一个子串的起始位置，也可以不选择。因此，总共有 2^n 种情况。对于每种情况，我们需要判断其是否是回文串，需要 O(n) 的时间复杂度。因此，总时间复杂度是 O(n * 2^n)。
空间复杂度：O(n)，其中 n 是字符串的长度。主要是用于存储回溯过程中的中间结果。
京公网安备 11010502036488号