本周是课程的第三周，我们学习了递归、分治、树、图的遍历等算法。
其中，树是学习的关键点，包括树的遍历、前中后序遍历的特点。树按层遍历、按深度优先方式遍历等。
作业题目如下：
23. Merge k Sorted Lists
class Solution { public ListNode mergeKLists(ListNode[] lists){ if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2){ return mergeTwoLists(lists[0],lists[1]); } int mid = lists.length/2; ListNode[] l1 = new ListNode[mid]; for(int i = 0; i < mid; i++){ l1[i] = lists[i]; } ListNode[] l2 = new ListNode[lists.length-mid]; for(int i = mid,j = 0; i < lists.length; i++, j++){ l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = null; if (l1.val <= l2.val){ head = l1; head.next = mergeTwoLists(l1.next, l2); } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; } }
47. Permutations II
class Solution { private List<List<Integer>> res = new ArrayList<>(); private Set<String> set = new HashSet<>(); public List<List<Integer>> permuteUnique(int[] nums) { // 回溯 backtrack(nums, new ArrayList<>()); return res; } private void backtrack(int[] nums, List<Integer> idxList) { // 如果所有元素都排列过 if (idxList.size() == nums.length) { List<Integer> list = new ArrayList<>(); // 通过索引list，构建元素list for (int index : idxList) list.add(nums[index]); if (!set.contains(list.toString())) { set.add(list.toString()); res.add(list); } return; } for (int i = 0; i < nums.length; i++) { // 如果nums[i]已经排序过，则跳过 if (idxList.contains(i)) continue; idxList.add(i); backtrack(nums, idxList); idxList.remove(idxList.size() - 1); } } }
