25. K 个一组翻转链表

用双指针,prev 和 end,当 end 不为 null 时候,就不断翻转。

前 end 移动 k 个,如果 end 已经是 null了,就 break。

然后设置一个 start,指向反转数组头部,next 指针,指向 end 后续部分。

然后把 end 后续断开,防止翻转多了,随后用 start 为头节点翻转链表。

反转后 start 变成子链表的尾节点了。

之后 start.next = next 接上断开的部分。

start 和 end 指针更新到 k 个一组的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
ListNode end = dummy;

while (end != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode start = prev.next;
ListNode next = end.next;
end.next = null;
prev.next = reverse(start);
start.next = next;
end = start;
prev = start;
}
return dummy.next;
}

public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}

138. 随机链表的复制

先把每个节点的指包装新的节点放入 map 中。

然后再遍历,简历 next 和 random 指针。

最后返回 key 为 head 的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}

cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}
}

104. 二叉树的最大深度

每次递归左右最大深度加一,后序遍历。

1
2
3
4
5
6
7
8
9
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}

TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;

invertTree(root.left);
invertTree(root.right);
return root;
}
}

101. 对称二叉树

放入对称轴左右两次进行比较,判断不同的情况,如果对称机继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return compare(root.left, root.right);
}

public boolean compare(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
} else if (left != null && right == null) {
return false;
} else if (left == null && right != null) {
return false;
} else if (left.val != right.val) {
return false;
}

boolean leftRes = compare(left.left, right.right);
boolean rightRes = compare(left.right, right.left);
return leftRes && rightRes;
}
}

543. 二叉树的直径

就是统计两边最大深度的和加一,最后返回值再减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private int res;
public int diameterOfBinaryTree(TreeNode root) {
traverse(root);
return res - 1;
}

public int traverse(TreeNode root) {
if (root == null) {
return 0;
}
int left = traverse(root.left);
int right = traverse(root.right);
res = Math.max(res, left + right + 1);
return Math.max(left, right) + 1;
}
}

102. 二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(level);
}
return res;
}
}

108. 将有序数组转换为二叉搜索树

二叉搜索数节点大于左节点,小于右节点,中序遍历是递增的,数组中间值就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return traverse(nums, 0, nums.length - 1);
}

public TreeNode traverse(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = traverse(nums, left, mid - 1);
node.right = traverse(nums, mid + 1, right);
return node;
}
}

98. 验证二叉搜索树

中序遍历,用一个变量保存前一个节点的值,判断当前节点是否大于前一节点,不正确就直接返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private Integer prev = null;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}

if (prev != null && root.val <= prev) {
return false;
}
prev = root.val;

return isValidBST(root.right);
}
}

230. 二叉搜索树中第 K 小的元素

中序遍历,用全局计数器,记录遍历的数量,当计数器等于 0,就是结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private int res;
private int i;
public int kthSmallest(TreeNode root, int k) {
i = k;
traverse(root, k);
return res;
}
public void traverse(TreeNode node, int k) {
if (node == null) {
return;
}

traverse(node.left, k);
i--;
if (i == 0) {
res = node.val;
return;
}
traverse(node.right, k);
}
}

199. 二叉树的右视图

层序遍历,只添加每层最后一个元素。或者前序遍历,优先获得首次访问该层的右侧节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(level.get(level.size() - 1));
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<Integer> res = new ArrayList<>();

public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0);
return res;
}

void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}

// 只有第一次到达这一层时才会添加节点
if (res.size() == depth) {
res.add(root.val);
}

// 优先访问右子树
dfs(root.right, depth + 1);
dfs(root.left, depth + 1);
}

114. 二叉树展开为链表

后续遍历,先把左右变成右侧的链表,然后处理中间节点,把左节点变成右节点,再找到新右节点的终点,把旧的右节点接上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}

flatten(root.left);
flatten(root.right);

TreeNode rightNode = root.right;
root.right = root.left;
root.left = null;
TreeNode cur = root;
while(cur.right != null) {
cur = cur.right;
}
cur.right = rightNode;
}
}

105. 从前序与中序遍历序列构造二叉树

  1. 构建中序映射。
  2. 从前序列表获取根节点。
  3. 从中序映射获取根节点中序列表位置,将中序列表分为左子树和右子树。
  4. 构建左右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
private Map<Integer, Integer> inorderMap;
private int preIndex = 0;

public TreeNode buildTree(int[] preorder, int[] inorder) {
// 构建中序索引表
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}

// 开始构建树
return build(preorder, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int inLeft, int inRight) {
// 如果当前子树范围无效,返回空节点
if (inLeft > inRight) {
return null;
}

// 1. 从前序数组找到根节点
int rootValue = preorder[preIndex];
preIndex++;
TreeNode root = new TreeNode(rootValue);

// 2. 找到根节点在中序遍历中的位置
int rootIndex = inorderMap.get(rootValue);

// 3. 构建左子树
root.left = build(preorder, inLeft, rootIndex - 1);

// 4. 构建右子树
root.right = build(preorder, rootIndex + 1, inRight);

return root;
}
}

236. 二叉树的最近公共祖先

后序遍历

  1. 递归终止条件
    • root == null:走到空节点,返回 null
    • root == proot == q:找到 pq,返回当前节点。
  2. 在左右子树查找
    • 递归查找左右子树中的 pq
  3. 返回逻辑
    • 左右子树都找到:说明 pq 分布在左右两侧,当前节点就是 LCA。
    • 只找到一个:返回非空的节点。
    • 都没找到:返回 null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == q || root == p) {
return root;
}

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null && right == null) {
return left;
} else if (left == null && right != null) {
return right;
} else {
return null;
}
}
}

437. 路径总和 III

前缀和方法。记录从根节点到当前节点路径的前缀和 curr,然后看此前有没有前缀和为 curr - targetSum,有就表示之间存在一段路径的和为 targetSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> map = new HashMap<>();
map.put((long)0, 1);
return traverse(root, map, 0, targetSum);
}

public int traverse(TreeNode node, Map<Long, Integer> map, long curr, int targetSum) {
if (node == null) {
return 0;
}
curr += node.val;
int res = map.getOrDefault(curr - targetSum, 0);
map.put(curr, map.getOrDefault(curr, 0) + 1);
res += traverse(node.left, map, curr, targetSum);
res += traverse(node.right, map, curr, targetSum);
map.put(curr, map.getOrDefault(curr, 0) - 1);
return res;
}
}

124. 二叉树中的最大路径和

也是后序遍历,每次更新 max 值,为左右子树的最长路径 + 中间节点的值,函数每次返回当前节点的最大路径,要么是中间+左子树,要么是中间+右子树,只能一边,因为不能乱走哈哈哈。
注意,如果左右是负数,还不如不选,接直接是 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
traverse(root);
return max;
}

public int traverse(TreeNode node) {
if (node == null) {
return 0;
}

int left = Math.max(traverse(node.left), 0);
int right = Math.max(traverse(node.right), 0);
max = Math.max(max, left + right + node.val);
return Math.max(left, right) + node.val;
}
}

46. 全排列

回溯排序问题,可以用 used 数组保存是否访问状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
backtracing(new LinkedList<>(), nums, new boolean[nums.length]);
return res;
}

public void backtracing(LinkedList<Integer> path, int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
backtracing(path, nums, used);
path.removeLast();
used[i] = false;
}
}
}

78. 子集

子集需要 startIndex,每次都放入结果集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtracing(new LinkedList<>(), 0, nums);
return res;
}

public void backtracing(LinkedList<Integer> path, int startIndex, int[] nums) {
res.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtracing(path, i + 1, nums);
path.removeLast();
}
}
}

17. 电话号码的字母组合

回溯解决双重 for 循环,for 循环解决横向,递归解决纵向。index = 0 表示第一个字母,递归时候 index + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return res;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtracing(new StringBuilder(), numString, digits, 0);
return res;
}

public void backtracing(StringBuilder sb, String[] numString, String digits, int index) {
if (sb.length() == digits.length()) {
res.add(sb.toString());
return;
}

String str = numString[digits.charAt(index) - '0'];
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i));
backtracing(sb, numString, digits, index + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}

39. 组合总和

要剪枝!!!组合问题需要 startIndex 来去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtracing(0, target, 0, candidates);
return res;
}

public void backtracing(int sum, int target, int startIndex, int[] candidates) {
if (sum > target) {
return;
}
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}

for (int i = startIndex; i < candidates.length; i++) {
path.add(candidates[i]);
backtracing(sum + candidates[i], target, i, candidates);
path.removeLast();
}
}
}

22. 括号生成

不需要模板的 for 循环,因为每层只有两个选择,一定要用我也没办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtracing(new StringBuilder(), n, n);
return res;
}

public void backtracing(StringBuilder sb, int left, int right) {
if (left < 0 || left > right) {
return ;
}

if (left == 0 && right == 0) {
res.add(sb.toString());
return;
}


sb.append("(");
backtracing(sb, left - 1, right);
sb.deleteCharAt(sb.length() - 1);

sb.append(")");
backtracing(sb, left, right - 1);
sb.deleteCharAt(sb.length() - 1);
}
}