用双指针，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;
}
}
|
先把每个节点的指包装新的节点放入 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);
}
}
|
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;
}
}
|
每次递归左右最大深度加一，后序遍历。
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;
}
}
|
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;
}
}
|
放入对称轴左右两次进行比较，判断不同的情况，如果对称机继续递归。
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;
}
}
|
就是统计两边最大深度的和加一，最后返回值再减一。
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;
}
}
|
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;
}
}
|
二叉搜索数节点大于左节点，小于右节点，中序遍历是递增的，数组中间值就是
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;
}
}
|
中序遍历，用一个变量保存前一个节点的值，判断当前节点是否大于前一节点，不正确就直接返回 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);
}
}
|
中序遍历，用全局计数器，记录遍历的数量，当计数器等于 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);
}
}
|
层序遍历，只添加每层最后一个元素。或者前序遍历，优先获得首次访问该层的右侧节点。
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);
}
|
后续遍历，先把左右变成右侧的链表，然后处理中间节点，把左节点变成右节点，再找到新右节点的终点，把旧的右节点接上。
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;
}
}
|
- 构建中序映射。
- 从前序列表获取根节点。
- 从中序映射获取根节点中序列表位置，将中序列表分为左子树和右子树。
- 构建左右子树。
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;
}
int rootValue = preorder[preIndex];
preIndex++;
TreeNode root = new TreeNode(rootValue);
int rootIndex = inorderMap.get(rootValue);
root.left = build(preorder, inLeft, rootIndex - 1);
root.right = build(preorder, rootIndex + 1, inRight);
return root;
}
}
|
后序遍历
- 递归终止条件
root == null：走到空节点，返回 null。root == p 或 root == q：找到 p 或 q，返回当前节点。
- 在左右子树查找
- 返回逻辑
- 左右子树都找到：说明
p 和 q 分布在左右两侧，当前节点就是 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;
}
}
}
|
前缀和方法。记录从根节点到当前节点路径的前缀和 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;
}
}
|
也是后序遍历，每次更新 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;
}
}
|
回溯排序问题，可以用 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;
}
}
}
|
子集需要 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();
}
}
}
|
回溯解决双重 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);
}
}
}
|
要剪枝！！！组合问题需要 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();
}
}
}
|
不需要模板的 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);
}
}
|
