用双指针,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); } }
|